Friday, 15:45 - 16:10 h, Room: H 3013


Jonathan Kelner
Electrical flows, linear systems, and faster approximations of maximum flows, minimum s-t cuts, and multicommodity flows in undirected graphs

Coauthors: Paul Christiano, Aleksander Madry, Gary Miller, Richard Peng, Daniel Spielman, Shanghua Teng


In this talk, I'll describe a new collection of techniques for approximately solving maximum flow, minimum s-t cut, and multicommodity flow problems in capacitated, undirected graphs. Using these techniques, we obtain asymptotically faster algorithms for all three, breaking running time barriers that have stood for over 30 years.
For graphs with n vertices and m edges, I'll show how to compute \e-approximately maximum flows in time \o(m4/3)\p(1/\e) and \e-approximately minimum s-t cuts in time \o(m+n4/3)\p(1/\e). We do this by treating our 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.
I'll then discuss why generalizing this approach to the multicommodity setting requires more general classes of linear systems and iterative methods. Using these, we find \e-approximate solutions to the maximum concurrent flow problem with k commodities in time \o(m4/3\p(k,\e-1)).


Talk 2 of the invited session Fri.3.H 3013
"Flows, cuts, and sparsifiers" [...]
Cluster 2
"Combinatorial optimization" [...]


  The main criterion for them is your ability to repay any Wisconsin Payday Loans, they are not interested in your previous attempts, the current one is all that matters. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.