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

arXiv: https://arxiv.org/abs/2203.00671 · HTML: https://mlsanity.com/paper/2203.00671/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2022.

## Built on by (most cited first, 28 of 28)

- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Testing Calibration in Nearly-Linear Time](https://mlsanity.com/paper/2402.13187/) (2024)
- [Parameter identification in linear non-Gaussian causal models under general confounding](https://mlsanity.com/paper/2405.20856/) (2024)
- [Regularized Robustly Reliable Learners and Instance Targeted Attacks](https://mlsanity.com/paper/2410.10572/) (2024)
- [Graph Neural Modeling of Network Flows](https://mlsanity.com/paper/2209.05208/) (2022)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Accelerating Matroid Optimization through Fast Imprecise Oracles](https://mlsanity.com/paper/2402.02774/) (2024)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment](https://mlsanity.com/paper/2209.02905/) (2022)
- [Warm-starting Push-Relabel](https://mlsanity.com/paper/2405.18568/) (2024)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Fair Clustering via Alignment](https://mlsanity.com/paper/2505.09131/) (2025)
- [Robust Sublinear Convergence Rates for Iterative Bregman Projections](https://mlsanity.com/paper/2602.01372/) (2026)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Fair Correlation Clustering in Forests](https://mlsanity.com/paper/2302.11295/) (2023)
- [Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues](https://mlsanity.com/paper/2306.09128/) (2023)
- [An Analysis of On-the-fly Determinization of Finite-state Automata](https://mlsanity.com/paper/2308.14077/) (2023)
- [A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem](https://mlsanity.com/paper/2310.18446/) (2023)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)
- [Fast and Simple Densest Subgraph with Predictions](https://mlsanity.com/paper/2505.12600/) (2025)
- [Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair](https://mlsanity.com/paper/2508.06774/) (2025)
- [A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networking](https://mlsanity.com/paper/2512.10874/) (2025)
- [Graph Alignment Topology as an Inductive Bias for Grounding Detection](https://mlsanity.com/paper/2605.22963/) (2026)
- [A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p](https://mlsanity.com/paper/2607.03503/) (2026)

## Abstract (arXiv)

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 m1+o(1) time. Our algorithm builds the flow through a sequence of m1+o(1) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized mo(1) time using a new dynamic graph data structure. Our framework extends to algorithms running in m1+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.