
We present 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.
FOS: Computer and information sciences, Data structures, convex optimization, interior point methods, Maximum flow, Integer programming, Interior-point methods, Maximum flow; minimum-cost flow; data structures; interior point methods; convex optimization, data structures, Graph theory (including graph drawing) in computer science, Computer Science - Data Structures and Algorithms, Maximum flow; Minimum cost flow; Data structures; Interior point methods; Convex optimization, Data Structures and Algorithms (cs.DS), minimum-cost flow, maximum flow
FOS: Computer and information sciences, Data structures, convex optimization, interior point methods, Maximum flow, Integer programming, Interior-point methods, Maximum flow; minimum-cost flow; data structures; interior point methods; convex optimization, data structures, Graph theory (including graph drawing) in computer science, Computer Science - Data Structures and Algorithms, Maximum flow; Minimum cost flow; Data structures; Interior point methods; Convex optimization, Data Structures and Algorithms (cs.DS), minimum-cost flow, maximum flow
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 67 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 1% |
