# An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2013.

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

- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Generalized Gradient Norm Clipping & Non-Euclidean (L0,L1)-Smoothness](https://mlsanity.com/paper/2506.01913/) (2025)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Clarifying Shampoo: Adapting Spectral Descent to Stochasticity and the Parameter Trajectory](https://mlsanity.com/paper/2602.09314/) (2026)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [Faster Acceleration for Steepest Descent](https://mlsanity.com/paper/2409.19200/) (2024)
- [Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning](https://mlsanity.com/paper/2507.04406/) (2025)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice](https://mlsanity.com/paper/2110.02750/) (2021)
- [Expander Hierarchies for Normalized Cuts on Graphs](https://mlsanity.com/paper/2406.14111/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [Smooth Quadratic Prediction Markets](https://mlsanity.com/paper/2505.02959/) (2025)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)
- [From Spectral to Frobenius: When Muon Loses Its Spectral Implicit Bias](https://mlsanity.com/paper/2610.20112/) (2026)

## Abstract (arXiv)

In this paper, we introduce a new framework for approximately solving flow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for the maximum s-t flow and maximum concurrent multicommodity flow problems. For graphs with n vertices and m edges, it allows us to find an ε-approximate maximum s-t flow in time O(m1+o(1)ε-2), improving on the previous best bound of tildeO(mn1/3 poly(1/ε)). Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with k commodities in O(m1+o(1)ε-2k2) time, improving on the existing bound of tildeO(m4/3 poly(k,ε-1). Our algorithms utilize several new technical tools that we believe may be of independent interest: - We give a non-Euclidean generalization of gradient descent and provide bounds on its performance. Using this, we show how to reduce approximate maximum flow and maximum concurrent flow to the efficient construction of oblivious routings with a low competitive ratio. - We define and provide an efficient construction of a new type of flow sparsifier. In addition to providing the standard properties of a cut sparsifier our construction allows for flows in the sparse graph to be routed (very efficiently) in the original graph with low congestion. - We give the first almost-linear-time construction of an O(mo(1))-competitive oblivious routing scheme. No previous such algorithm ran in time better than tildeOmega(mn). We also note that independently Jonah Sherman produced an almost linear time algorithm for maximum flow and we thank him for coordinating submissions.