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>