Technion
 
The Operations Research seminar will be held on December 13, 2010
 
________________________________________________________________________________
 
Speaker: Aleksander Madry from MIT, USA
 
Title: Electrical Flows, Laplacian Systems, and Faster Approximation of
Maximum Flow in Undirected Graphs
 
Time and place: at 12:30 in Bloomfield-527


For an abstract please see below or the website of the Operations Research seminar:

 <http://iew3.technion.ac.il/Labs/Seminar/seminar.php?7>

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.

 
________________________________________________________________________________
 
You can watch the rest of the seminar plan at our web site
 
________________________________________________________________________________
 
Virtually, seminar manager
 
_______________________________________________
Or-seminar mailing list
 <Or-seminar@technion.ac.il>
 <http://iemm1.technion.ac.il/mailman/listinfo/or-seminar>
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from:  <levinas@techunix.technion.ac.il>