Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs
Speaker: Jonathan Kelner, CSAIL, MIT
Date: Tuesday, September 28 2010
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , imbe@mit.edu
Relevant URL: 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.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in September 2010
