Regular polygon

Mathematical analysis

Maximum flow problem

Programming language

Time complexity

Approximation algorithm

Geometry

Minimum-cost flow problem

Scaling

Combinatorics

Directed graph

Mathematics

Mathematical optimization

Data structure

Flow (mathematics)

Flow network

Amortized analysis

Computer science

Separable space

Discrete mathematics

Bounded function

Minimum cut

We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized $m^{o(1)}$ time using a new dynamic graph data structure. Our framework extends to algorithms running in $m^{1+o(1)}$ time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time