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

By Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, Aaron Sidford. 2013

284 citations recorded by the source corpus.

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 e-approximate maximum s-t flow in time O(m1+o(1)e-2), improving on the previous best bound of O(mn1/3poly(e-1)). Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with k commodities in O(m1+o(1)e-2k2) time, improving on the existing bound of O(m4/3poly(k>,e-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 oblivious routing. • We define and provide an efficient construction of a new type of flow sparsifier. Previous sparsifier constructions approximately preserved the size of cuts and, by duality, the value of the maximum flows as well. However, they did not provide any direct way to route flows in the sparsifier G' back in the original graph G, leading to a longstanding gap between the efficacy of sparsification on flow and cut problems. We ameliorate this by constructing a sparsifier G' that can be embedded (very efficiently) into G with low congestion, allowing one to transfer flows from G' back to G. • 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 Ω(mn). By reducing the running time to almost-linear, our work provides a powerful new primitive for constructing very fast graph algorithms. The interested reader is referred to the full version of the paper [8] for a more complete treatment of these results.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

In Optimization & Training

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “For instance, if the LMO is max-flow, it could have almost linear runtime while the corresponding projection would require cubic runtime quadratic programming (Kelner et al., 2014).”
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow (2014, result): “Leveraging these fast Laplacian system solvers Christiano, Kelner, M ˛ adry, and Spielman [4] showed how to compute (1−) approximations to the maximum flow problem on undirected graphs iñ improved the running time tõ This line of work culminated in recent results of Sherman [36] and Kelner, Lee, Ore”
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems (2013, methodology): “in nearly-linear time, such systems have been used to create the fastest algorithm for a variety of problems ranging from max flow [23] to sampling random spanning trees [9] and much more.”
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time (2022, methodology): “…paradigm achieved several successes, including O ( m(cid:2) − 1 ) time (1+ (cid:2) ) -approximate undirected max-ﬂow and multicommodity ﬂow [16, 33, 43, 41, 42], and an m 4 / 3 + o (1) U 1 / 3 time algorithm for bipartite matching and unit capacity max-ﬂow [40, 38, 37, 32, 5], and pm 1+ o (1)…”