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>