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

Speaker(s)

Aleksander Madry

Affiliation

Microsoft Research New England i EPFL

Date

Dec. 8, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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.

---