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
 
                                Aleksander Madry
                                     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>