Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
The maximum flow problem and its dual, the minimum s-t cut problem, are two of the most fundamental and extensively studied problems in Operations Research and Optimization. They have many direct applications and are also often used as subroutines in other algorithms.
In this talk, I'll describe a fundamentally new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then use this technique to develop the asymptotically fastest-known algorithm for solving this problem. For graphs with n vertices and m edges, the algorithm computes epsilon-approximate maximum flows in time \tilde{O}(m^{4/3})poly(1/epsilon) and computes epsilon-approximate minimum s-t cuts in time \tilde{O}(m+n^{4/3})poly(1/epsilon).
We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
This is joint work with Paul Christiano, Aleksander Madry, Daniel Spielman, and Shanghua Teng.
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
The maximum flow problem and its dual, the minimum s-t cut problem, are two of the most fundamental and extensively studied problems in Operations Research and Optimization. They have many direct applications and are also often used as subroutines in other algorithms.
In this talk, I'll describe a fundamentally new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then use this technique to develop the asymptotically fastest-known algorithm for solving this problem. For graphs with n vertices and m edges, the algorithm computes epsilon-approximate maximum flows in time \tilde{O}(m^{4/3})poly(1/epsilon) and computes epsilon-approximate minimum s-t cuts in time \tilde{O}(m+n^{4/3})poly(1/epsilon).
We compute these flows by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
This is joint work with Paul Christiano, Aleksander Madry, Daniel Spielman, and Shanghua Teng.