Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

By Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng. Symposium on the Theory of Computing, 2010

372 citations recorded by the source corpus.

We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time ~O(mn1/3ε-11/3). A dual version of our approach gives the fastest known algorithm for computing a (1+ε)-approximately minimum s-t cut. It takes ~O(m+n4/3ε-16/3) time. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time ~O({m√nε-1), and approximately minimum s-t cuts in time ~O(m+n3/2ε-3).

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/af1afe809c106ed2618fc2ae14b696f672fc4bc1

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints (2018, methodology): “To this end, we build on a long line of prior work that treats constrained optimization as a two-player game [e.g. Christiano et al., 2011, Arora et al., 2012, Rakhlin and Sridharan, 2013, Kearns et al., 2017, Narasimhan, 2018, Agarwal et al., 2018].”
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods (2017, methodology): “This problem can be solved in time Õ(mn) using the multiplicative weights framework as applied in [47], [48].”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, background): “…optimization via the introduction of a slack variable: min θ∈Θ,ξ∈R ξ (4) s.t. ξ ≥ gi (θ) for all i ∈ 1, . . . ,m. Correspondingly, one can transform a robust problem to a constrained one at the cost of an extra bisection search (e.g. Christiano et al., 2011; Rakhlin and Sridharan, 2013).”
Two-Player Games for Efficient Non-Convex Constrained Optimization (2018, background): “…fact that robust optimization can be reformulated as constrained optimization via the introduction of a slack variable ξ : Correspondingly, one can transform a robust problem to a constrained one at the cost of an extra bisection search [e.g. Christiano et al., 2011, Rakhlin and Sridharan, 2013].”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs , and its Multicommodity Generalizations (2013, background): “Following this, Lee, Rao, and Srivastava [16] proposed another iterative algorithm that uses electrical flows, but in a way that was substantially different than in [7].”
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time (2022, methodology): “The Laplacian paradigm achieved several successes, including Õ(m −1) time (1+ )-approximate undirected max-flow and multicommodity flow [16, 33, 43, 41, 42], and an m(4)/3+o(1)U 1/3 time algorithm for bipartite matching and unit capacity max-flow [40, 38, 37, 32, 5], and pm time unweighted p-norm mi”