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

Li Chen; Rasmus Kyng; Yang P. Liu; Richard Peng; Maximilian Probst Gutenberg; Sushant Sachdeva

Source-linked AI summary

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

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

arXiv:2203.00671v2Mar 1, 2022cs.DS

TL;DR

General-graph min-cost flow had running times far from linear. This paper develops a potential-reduction IPM and adaptive dynamic data structures for approximate undirected min-ratio cycles, yielding almost-linear-time exact min-cost and maximum-flow algorithms.

Problem
General-graph min-cost flow lacked an almost-linear running-time bound despite progress from specialized data structures.
Method
A potential-reduction IPM reduces min-cost flow to slowly changing undirected min-ratio cycle instances, supported by randomized dynamic data structures that maintain approximate cycles and route circulations.
Results
Exact min-cost flow is computed in m1+o(1) log U log C time with high probability, while maximum flow is computed in m1+o(1) log U time with high probability.
Takeaways & Limitations
The framework provides the first almost-linear-time algorithm for min-cost flow in general graphs and supports adaptive, efficiently maintained approximate cycle computations.
Takeaways & Limitations
The precise data structure described for the earlier approach works only for oblivious adversaries; later data structures must address adaptivity in the cycle sequence.

Abstract

from arXiv · show

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.

1 Introduction

The paper presents the first almost-linear-time exact min-cost-flow algorithm in general graphs, using an IPM built from stable approximate undirected min-ratio cycle instances and dynamic graph data structures. The framework also yields almost-linear-time algorithms for max-flow and broader convex-flow applications.

The paper gives the first almost-linear-time algorithm for exact min-cost flow in general graphs, achieving m1+o(1) log U log C time with high probability.This improves the prior general-graph bound, which remained far from linear.
m1+o(1) log U time computes maximum flow between two vertices with integral capacities in [1, U], with high probability.The max-flow result follows from a direct reduction to min-cost flow.
The framework extends to general edge-separable convex objectives, covering regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression.The paper also applies the flow results to bipartite matching, shortest paths, negative-cycle detection, connectivity, and cut problems.
The new potential-reduction IPM reduces min-cost flow to m1+o(1) slowly changing undirected minimum-ratio cycle instances.Each instance uses positive edge lengths and signed gradients, and seeks a circulation minimizing a gradient-to-length ratio.
A randomized dynamic data structure returns mo(1)-approximate min-ratio cycles and processes routing, updates, and significant-flow detection in amortized mo(1) time.The instances are represented using a collection of mo(1) spanning trees and exploit their stability.
Dynamic spanners with explicit short path embeddings support efficient edge reduction under insertions, deletions, and vertex splits without losing useful circulation witnesses.The maintained spanner has eO(n) edges, path embeddings of length mo(1), and mo(1) amortized edge changes per update.
The data structures must handle adaptive, non-oblivious sequences of min-ratio cycle instances because later instances depend on cycles returned by the algorithm.This adaptivity creates additional challenges beyond maintaining slowly changing inputs.

2 Overview

The paper reduces min-cost flow to slowly changing undirected minimum-ratio cycle instances and maintains approximate solutions with a recursive dynamic data structure. Hierarchical core graphs, spanners, randomized embeddings, and controlled rebuilding yield almost-linear amortized performance despite adaptive updates.

2.1 Computing Min-Cost Flows via Undirected Min-Ratio Cycles: m1+o(1) undirected minimum-ratio cycle instances suffice for high-accuracy min-cost flow, replacing the usual ℓ2 subproblems with ℓ1 minimization.The potential-reduction IPM tolerates mo(1)-approximate solutions, unlike approaches requiring near-exact iterates.
2.1 Computing Min-Cost Flows via Undirected Min-Ratio Cycles: A witness circulation f*−f provides the required negative min-ratio direction, with g(f)⊤∆/∥L∆∥1 ≤−eΩ(1).This witness is essential for proving randomized data structures remain effective under apparently adaptive IPM updates.
2.2 High Level Overview of the Data Structure for Dynamic Min-Ratio Cycle: The dynamic structure maintains mo(1) spanning trees and represents each returned cycle using mo(1) off-tree edges and connecting paths.Low-stretch tree cycles provide approximate solutions, while partial rebuilding adapts embeddings to changing lengths and gradients.
2.2 High Level Overview of the Data Structure for Dynamic Min-Ratio Cycle: m1−o(1)/ki updates survive at level i, while rebuilding costs m1+o(1)/ki−1, giving amortized mo(1) update cost against oblivious adversaries.The resulting dynamic min-ratio structure achieves mo(1) query time in that setting.
2.3 Building Core Graphs: Core graphs contract forest components to eO(m/k) vertices, then spanners reduce their edge count to eO(m/k) while preserving short path embeddings.The construction combines low-stretch decompositions, portal routing, and spanners, and supports eO(m/k) edge updates before rebuilding.
2.6 The Rebuilding Game: The rebuilding game limits the cost of failures, and the combined structure finds update cycles in amortized mo(1) time per cycle update.If quality degrades, recomputing the LSD collection reduces the width norm by a constant factor, permitting at most eO(1) recomputations.

3 Preliminaries

The preliminaries establish notation for graphs, flows, paths, embeddings, dynamic graphs, and vector operations, then state supporting tools such as Chernoff bounds, low-stretch trees, and dynamic trees.

General notation: The notation section defines entrywise products and absolute values, inner products, approximate equality, and positive-vector comparison.Diagonal matrices commonly represent vectors, while x ≈_α y means coordinatewise multiplicative approximation for positive vectors.
Graphs and flows: Graphs are directed multigraphs with implicit edge directions, incidence matrix B, m edges, and n vertices.A flow f routes demand d when B^T f = d; each edge also has a unit demand vector.
Dynamic graphs: Dynamic graphs evolve through batches of edge insertions, deletions, and possibly vertex splits.Updates are encoded explicitly, and the total encoding size across batches is polynomially bounded in the initial graph size.
Paths and flows: Paths in forests define routed unit flows whose absolute-value vectors indicate the tree paths and compose consistently across consecutive segments.For vertices u, v, and w in one forest component, p(F[u,v]) + p(F[v,w]) = p(F[u,w]).
Supporting tools: Low-stretch spanning trees provide efficiently constructible trees with polylogarithmic average stretch, and Chernoff bounds control sums of independent bounded random variables.The stated static LSST algorithm runs in eO(m) time.
Graph embeddings: Graph embeddings map each source edge to a path in a host graph and measure edge and vertex congestion, path length, and routed flow vectors.The embedding flow vector satisfies B^T Π_G→H(e) = b_e.
Dynamic trees: Dynamic tree structures support tree updates, path queries, signed and positive flow updates, and detection operations in amortized eO(1) time per supported operation.The maintained tree can change by edge insertion or deletion while preserving the tree invariant.

4 Potential Reduction Interior Point Method

The section develops a primal-only potential-reduction interior-point method for min-cost flow that repeatedly augments along approximate undirected minimum-ratio cycles. With suitable potential reduction and initialization, it reaches near-optimal cost and supports exact recovery.

Potential design: The method uses a potential function with an x^-α barrier because quasipolynomial length bounds are unavailable for the standard logarithmic barrier.Here α = 1/(1000 log mU), and the method assumes the optimal value F* is known or found by binary search.
Guarantee: The algorithm performs eO(mκ^-2) iterations and ends with c^T f^(t) ≤ c^T f* + (mU)^-10.The potential reaches -O(m log m), after which Lemma 4.1 converts the potential bound into the stated cost guarantee.
Iterative method: Each iteration approximately solves an undirected minimum-ratio cycle problem using approximated gradients and lengths, then adds a scaled circulation to the current flow.The update preserves circulation feasibility and uses η = κ^2/(50 · |ĝ^TΔ|).
Progress and stability: The direction from the current flow to the optimum is a sufficiently good witness circulation, enabling approximate cycle solutions to reduce the potential by Ω(κ^2) per iteration.This witness also makes the sequence of cycle instances stable enough for the later dynamic data structure.
Exact recovery: A nearly optimal flow can be rounded or postprocessed to recover an exact optimal flow, with the recovery procedure running in O(m) time.The construction first initializes a flow with potential O(m log mU) on a larger graph.

5 Decremental Spanner and Embedding

This section constructs decremental sparsifiers and embeddings that maintain a sparse representation of a changing graph while controlling path lengths, congestion, and re-embedding changes. The resulting structures support the dynamic min-ratio-cycle data structure.

Sparsifier and embedding: The maintained sparsifier has at most eO(n) edges, while its embedding provides bounded path length and vertex congestion.The embedding guarantees length(ΠG→H) ≤ (γl)^O(L) and vcong(ΠG→H) ≤ (γc)^O(L)Δmax(G).
Re-embedding: The algorithm reports a small set D(t) containing the edges whose embedding status changes after each update batch.Edges outside D(t) do not newly appear on embedding paths at the current stage.
Parameter choice: Choosing L = (log m)^1/4 makes the amortized runtime, embedding lengths, and reported-change size all O(γs), with γs = exp(O(log^3/4 m log log m)).These guarantees depend on the number of updates in each batch rather than its potentially larger encoding size.
Initialization: The sparsification procedure produces a sparse subgraph and an embedding of length at most γl and vertex congestion at most 2γcΔmax(G) with high probability.The procedure runs in eO(mγl) time.
Runtime: The dynamic structure has initialization time eO(mγl) and amortized update time eO(n^1/L(γcγl)^O(L)Δmax(G)).Its maintained sparsifier changes by eO(n^1/L) edges per update, and D(t) has amortized size eO(n^1/L(γcγl)^O(L)).

6 Data Structure Chain

The data structure chain maintains approximate minimum-ratio cycles under stable updates by recursively reducing graph size with forests, embeddings, and spanners. Its guarantees rely on a hidden stable-flow witness rather than fully adaptive-update robustness.

Stability assumption: The update model requires a hidden circulation and upper bounds whose changes remain stable, even though these witnesses are not exposed to the data structure.The witness upper bounds may increase by at most a factor of 2 except on explicitly updated edges, and lengths remain quasipolynomially bounded.
Dynamic cycle maintenance: The data structure dynamically maintains approximate undirected minimum-ratio cycles under hidden stable-flow chasing updates.It supports gradient and length updates together with cycle queries and efficient circulation routing.
Queries: A query returns an m^o(1)-approximate cycle represented by m^o(1) tree paths and explicitly listed off-tree edges.The maintained collection contains s = O(log n)^d spanning trees, with d = O(log^1/8 m).
Performance: Over τ stages, the structure succeeds with high probability and has total runtime m^o(1)(m + Q).The cycle representation can be added to the flow efficiently using link-cut trees.
Recursive reduction: The recursive chain reduces graphs using low-stretch spanning forests, vertex contraction, spanners, and multiplicative-weights distributions over partial tree routings.The resulting distribution gives average stretch eO(1) on every edge, while the low-stretch decomposition is maintained deterministically in eO(m) total time.

7 Routings and Cycle Quality Bounds

This section develops dynamic core and sparsified-core graphs that route witness circulations through a branching tree-chain while preserving useful cycle-quality guarantees. The resulting structure supports high-probability approximate circulation queries and efficient rebuilding.

Branching tree-chain: Theorem 7.1 maintains a branching tree chain and outputs a sparse circulation at each stage under hidden stable-flow chasing updates.The chain uses s = O(log n)d trees, and the circulation is represented by exp(O(log^7/8 m log log m)) off-tree edges and tree paths.
Cycle quality: The output circulation satisfies B^T∆ = 0 and achieves a quality parameter κ = exp(−O(log^7/8 m log log m)).
Runtime and rebuilding: Theorem 7.1 succeeds with high probability in total runtime (m + Q)m^o(1), while levels i through d can be rebuilt in m^1+o(1)/k^i time.
Dynamic core graphs: Dynamic core graphs preserve valid circulations and length upper bounds while controlling update recourse and keeping one sampled core’s widths small with high probability.The construction maintains O(log n) trees and forests, and its runtime is eO(mk).
Sparsified core graphs: Sparsified core graphs increase total update size by at most m^o(1), preserve hidden stable-flow chasing updates, and maintain small widths across levels.Validity follows because the transformed circulation remains a circulation and transformed widths remain length upper bounds.

G .DynamicSparseCore(G, U(t)

This section maintains and analyzes fundamental chain cycles across recursively reduced graphs. Explicit gradients and conservative length overestimates let the algorithm select a high-quality cycle while preserving correctness through repeated lifting.

Recursive representation: The tree-chain recursively passes circulations, lengths, gradients, and embeddings between core and sparsified-core graphs.Each level consists of a core graph, a sparsified core, and an embedding back into the core.
Cycle construction: A sparsifier cycle combines an off-tree edge with its replacement path, while its preimage is a fundamental chain cycle in the original graph.
Cycle selection: The algorithm explicitly maintains total gradients and length overestimates for fundamental chain cycles, then returns the cycle with best estimated quality.
Correctness: Gradient correctness ensures each core cycle and its lifted preimage have identical total gradients.
Correctness: Length overestimates are at least the lengths of lifted preimage cycles, so selecting by estimated quality remains conservative.

8 Rebuilding Data Structure Levels

The rebuilding game converts hidden width changes into a deterministic strategy for rebuilding tree-chain levels. Its counter-based strategy bounds fixing steps and yields an almost-linear total runtime for the dynamic min-ratio-cycle structure.

Game model: The rebuilding game models rounds in which hidden weights may force fixes that rebuild a chosen level and every higher level.A fix at level i costs C_r m/k^i time and resets previous rebuild times for levels j ≥ i.
Runtime bound: A deterministic strategy completes T rounds in O(C_r K^d γ_g(m + T)) time.
Strategy: The strategy uses round and fixing counters to preempt forced rebuilds and assign losses to the largest eligible level.
Fixing-step control: The strategy guarantees fix_0 < 2K, while higher-level fixing counts are also bounded by 2K.
Application: Combining the rebuilding strategy with Theorem 7.1 gives a dynamic min-ratio-cycle data structure running in (m + Q) exp(O(log^7/8 m log log m)) time.

9 Computing the Min-Cost Flow via Min-Ratio Cycles

The min-cost flow algorithm maintains approximate lengths, gradients, and dynamically changing tree structures while repeatedly applying approximate min-ratio cycle updates. Its analysis establishes high-probability termination and almost-linear total runtime, followed by rounding to an exact flow.

Algorithm implementation: The algorithm maintains approximate flows, lengths, gradients, residual-cost estimates, and dynamic tree structures throughout MinCostFlow.Updates are triggered when dynamic data structures detect sufficiently large edge changes, and the hidden stable-flow chasing structure maintains trees and approximate min-ratio cycles.
Algorithm implementation: Each update represents a circulation through a small number of off-tree edges and tree paths, then scales it to a prescribed gradient change.The circulation is represented using m^o(1) off-tree edges and paths, with scaling chosen so its inner product with the gradient equals -κ^2α^2/800.
Stability analysis: The maintained lengths and gradients remain approximately correct, while the residual cost changes by at most a 1+ε factor between rebuilds.The data structure rebuilds every εm iterations, and the analysis bounds the accumulated change in residual cost over each such interval.
Iteration and correctness bounds: The algorithm terminates after eO(mκ^-2α^-2) iterations, with the dynamic data structure succeeding with high probability.The iteration bound follows from the interior-point analysis and the hidden stable-flow chasing guarantees.
Runtime and exactness: The total update volume is bounded through the per-iteration circulation progress, enabling the data structure to run in m^1+o(1) total time.The final proof combines the update-batch bound with the dynamic data structure runtime and then rounds the high-accuracy flow to an exact min-cost flow.

10 General Convex Objectives

The paper extends its flow framework to separable convex objectives by using self-concordant barriers and a staged potential-reduction method. Under quasipolynomial boundedness assumptions, the resulting algorithm achieves almost-linear time and high accuracy across several applications.

General convex-flow formulation: The generalized problem minimizes an edge-separable convex objective h(f)=Σ_e h_e(f_e) over flows satisfying B^⊤f=d.Each edge contributes a convex function, and feasibility is imposed by routing the prescribed demand.
Assumptions: The method assumes accessible barrier gradients and Hessians, polynomially bounded inputs, feasible initialization, and quasipolynomially bounded Hessians.These assumptions ensure that the lengths and gradients encountered by the algorithm remain controlled.
Self-concordance: Scaling α^-1ζ_e/4 yields a self-concordant function, supporting the interior-point analysis for the reduced convex objectives.The paper derives the required derivative identities after optimizing the auxiliary variable y_e(f_e).
Main guarantee: Theorem 10.13 gives an m^1+o(1)-time flow with objective value at most optimum plus exp(-log^C m) for any fixed constant C.The guarantee applies under the stated barrier and boundedness assumptions.
Applications: The framework applies to p-norm flows, p-norm isotonic regression, entropy-regularized optimal transport, and matrix scaling.The stated applications include arbitrary p∈[1,∞] for isotonic regression and high-accuracy matrix scaling with near-unit row and column sums.

A.1 Maximum Flow

The related-work discussion situates the paper among combinatorial, numerical, and interior-point approaches to maximum and minimum-cost flow. Its distinction is using dynamic tree-like structures with undirected min-ratio cycles rather than electrical-flow data structures.

Maximum-flow approaches: Classical maximum-flow research developed augmenting-path, push-relabel, and pseudo-flow methods, alongside dynamic trees for identifying bottleneck edges.These approaches include both weakly and strongly polynomial algorithms, with dynamic trees supporting fast bottleneck operations.
Position of this work: The paper instead uses dynamic tree-like data structures and undirected minimum-ratio cycles, requiring Ω(m) iterations rather than the smaller iteration counts common after the Laplacian paradigm.Its algorithm can be viewed as identifying approximate bottlenecks under an interior-point-motivated definition.
Numerical and Laplacian methods: Interior-point methods combined with fast Laplacian solvers initiated a numerical approach to flow problems and produced eO(m^1.5 log^2 U) min-cost flow algorithms.The Laplacian paradigm connects the linear systems arising in single-commodity flow IPMs to graph Laplacians.
Recent progress: Recent electrical-flow data structures improved runtimes for dense and sparse flow settings, while approximation methods reached eO(mε^-1) for (1+ε)-approximate max-flow.Other interior-point advances reduced iteration complexity from m^1/2 toward n^1/2 or m^1/3+o(1) in selected settings.
Min-cost flow context: Strongly polynomial min-cost flow algorithms often use directed minimum-mean cycles, whereas this work studies undirected minimum-ratio cycles in a different algorithmic framework.Earlier scaling methods generally handled only capacities or costs in their strongest guarantees.

B.2 Proof of Theorem 5.11

The proof constructs a hierarchy of graphs whose edge counts shrink geometrically while preserving expander structure. Expander decompositions and edge-deletion arguments establish the claimed bounds at every level.

Expander decomposition: The construction uses an expander decomposition that partitions vertices into induced ψ-expanders while leaving at most one quarter of edges outside the expanders.The decomposition runs in O(m log^7(m)) time with high probability for any fixed polynomial failure exponent.
Recursive construction: At each level, the graph is augmented with 2^i self-loops before computing the next expander decomposition.The algorithm repeatedly applies this decomposition to the augmented graph G̃_i.
Edge-count invariant: Each graph G_i has at most 2^i n edges at initialization, providing the base edge-count bound for the hierarchy.This is stated as Claim B.2 for every level i.
Inductive proof: The induction shows that G_{i-1} contains at most 2^{i-1}n edges because its inter-part edges are bounded by the expander decomposition and its self-loops contribute a controlled amount.The proof uses the fact that each graph can only lose edges after initialization.
Degree property: For vertices inside an expander part, the minimum-degree property follows by relating degrees in G_i to internal edges of the augmented graph.The proof identifies the relevant internal degree through the expander decomposition representation.

B.3 Proof of Lemma 6.5

The proof constructs a branch-free root set and an associated forest by deleting selected tree edges between adjacent roots. Ordering deleted edges by congestion yields a forest with low total stretch while dynamic root updates add only logarithmically many auxiliary roots.

Forest construction: Branch-free roots ensure exactly |R| − 1 adjacent root pairs, allowing one tree edge to be removed on each corresponding path.The forest then has exactly |R| connected components, each containing a unique root.
Congestion ordering: Ordering tree edges by increasing congestion makes the resulting forest have low total stretch.This is the central guarantee of the construction.
Stretch analysis: The construction defines congestion through tree paths and exploits sorted congestion, disjoint root-to-root paths, and the branch-free invariant in its stretch analysis.These properties supply the three proof ingredients cited for the relevant inequalities.
Initial roots: O(m/k) roots suffice initially, and the tree decomposition makes this root set branch-free with bounded component boundary weights.The decomposition also provides the structural conditions used for item 4 of Lemma 6.5.
Dynamic root maintenance: Each vertex insertion adds at most O(log^2 n) additional roots, controlling how many potential roots an edge can be assigned to.The auxiliary tree replaces heavy chains with balanced binary trees, giving logarithmic height.
Dynamic root maintenance: A heavy-light-based auxiliary tree of height O(log^2 n) preserves branch-freeness when ancestors are added to the root set.For any vertex subset R, the expanded set R↑TH is branch-free and supports consistent forest-root assignments.

B.4 Proof of Lemma 6.6

The proof combines multiplicative weight updates with repeated tree and forest constructions, then uses cost and capacity scaling to reduce general min-cost flow instances to polynomially bounded ones. The resulting exact solver inherits the runtime of the bounded-instance algorithm up to logarithmic factors.

Stretch analysis: The proof bounds the accumulated stretch through an iterative inequality and obtains the target logarithmic bound after taking logarithms.The intermediate analysis repeatedly applies the stated exponential inequality.
Weight-update construction: t = 10kW log^2 n iterations suffice for the multiplicative weight update sequence of weights, trees, forests, and stretch overestimates.The distribution λ is uniform over these t iterations.
Scaling reduction: O(log mU log C) scaling reductions convert integral min-cost flow instances into polynomially bounded cost and capacity instances.The reduction preserves exact solvability with runtime O(TA(m) log m log mU log C).
Runtime consequence: TMCC(m, poly(m), poly(m)) = m^(1+o(1)) follows directly from the paper’s main theorem.This is the polynomially bounded min-cost circulation runtime corollary.

C.1 Reduction to Polynomially Bounded Cost Instances

The cost-scaling scheme repeatedly improves ε-optimal integral circulations by solving polynomial-cost problems on rounded residual graphs. After O(log C) halvings, the circulation is exact, and dual solutions can be recovered within the same asymptotic runtime.

Runtime: O(TA(m) log C + m log C) time suffices for cost scaling when bounded-cost instances are solved in TA(m) time.The per-iteration overhead includes constructing the rounded residual graph and updating primal and dual variables.
Optimality certificate: 1/(n + 1)-optimality certifies exact optimality for feasible integral circulations with integral costs.The proof uses integrality: any negative residual cycle would have cost at most −1, contradicting the ε-optimality bound.
Cost scaling: Each cost-scaling iteration rounds reduced residual costs and computes primal and dual optima for the resulting polynomially bounded instance.The rounded costs use integral multiples of ε/m^8 and can be restricted to a bounded range.
Dual recovery: An additional routine extracts an optimal dual solution from the primal optimum by computing residual shortest-path distances.The primal-dual recovery runs in O(TMCC(m, C, U))-time.
Convergence: O(log C) iterations reduce ε from C to below 1/(n + 1), producing an exact minimum-cost circulation.The update invariant halves the optimality parameter at every iteration.

C.2 Reduction to Polynomially Bounded Capacity Instances

Capacity scaling handles large capacities by finding approximate negative-cycle augmentations, rounding residual capacities, and repeatedly improving the circulation. The scheme reduces arbitrary capacities to polynomially bounded capacities while preserving exact solvability through logarithmically many stages.

Polynomial capacity bounds: m^40-bounded capacities result after scaling rounded capacities by ⌈B/m^20⌉, making the rounded instance compatible with the bounded-capacity solver.The scaled solution can be recovered integrally for the capacity-rounded instance.
Termination: After O(log(CmU)) augmentations, the residual optimum is at least −0.1 in value, which identifies an exact optimum because integral residual optima are 0 or at most −1.Each iteration augments with a constant-approximate integral residual solution.
Approximate augmentation: An m^(1/2)-approximate circulation can be found in O(TA(m) log m)-time by locating a negative cycle with maximum bottleneck.Binary search over bottleneck capacities invokes unit-capacity min-cost circulation tests.
Capacity rounding: Capacity rounding preserves feasibility and yields a 1.1-approximate solution when the original optimum is bounded by a known negative estimate.Edges are rounded down to integral multiples of B/m^20 and capacities above mB are capped.
Runtime: O(TA(m) log m log mU + m log m log mU) time solves the large-capacity instance.The runtime combines approximate-solution computation, bounded-capacity augmentation, and instance-update overhead across all stages.

D Applications

The flow result yields almost-linear-time algorithms across flow variants, optimization problems, connectivity tasks, shortest paths, expanders, and dynamic graph maintenance. These reductions improve prior runtimes and extend high-accuracy algorithms to broader settings.

Extensions of Theorem 1.1: Almost-linear-time algorithms extend to vertex-capacity flows, flow diffusion, and a wide range of edge-cost functions.Vertex capacities and costs are handled by standard transformations, while flow diffusion replaces demands with vertex capacity constraints.
Extensions of Theorem 1.1: Near-linear-time algorithms compute weighted p-norm flows up to polynomially small error, beyond prior identity-weight restrictions.The problem minimizes ||Wf||_p subject to flow demands; prior work either required super-linear time or assumed W was the identity.
Bipartite Matching & Optimal Transport: The result gives almost-linear-time algorithms for worker assignment and entropically regularized optimal transport in bipartite graphs.Worker assignment runs in m1+o(1) log2 U time, while entropic regularization is used for optimal transportation applications in machine learning.
Applications: The framework yields almost-linear-time algorithms for matrix scaling with exponentially large scaling factors and p-norm isotonic regression on arbitrary DAGs.The isotonic regression algorithm achieves 1/poly(n) additive accuracy for all p ∈ [1, ∞), with runtime near-linear in the DAG's edge count.
Applications: The paper reports polynomial-factor runtime improvements for all cited problems.These improvements apply across the listed flow, optimization, connectivity, expansion, and dynamic-graph applications.