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

Prelegent(ci)

Aleksander Madry

Afiliacja

Microsoft Research New England i EPFL

Termin

8 grudnia 2011 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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.

---