The  Weizmann  Institute  of  Science
Faculty of Mathematics and Computer Science

Foundations of Computer Science Seminar

Lecture Hall, Room 1, Ziskind Building
on Sunday, December 12, 2010
at 11:00

Note unusual location/day/time

M.I.T.

will speak on

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

Abstract:
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 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}(mn^{1/3}\epsilon^{-11/3})$ and computes
$\epsilon$-approximate minimum $s-t$ cuts in time
$\tilde{O}(m+n^{4/3}\epsilon^{-16/3})$.

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.

---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Gershon Wolansky   <techm@math.technion.ac.il>
Announcement from: Diana Mandelik   <diana.mandelik@weizmann.ac.il>