Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

In this talk, I'll describe a 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.

Our approach is based on treating the 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, Jonathan Kelner, Daniel Spielman, and Shang-hua Teng.