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

 

Abstract:
\def\e{ε}
\def\p{\mathrm{poly}}
\def\o{Õ}
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" [...]

 

  There are three major facts that should be watched out for in all payday loans in the United States. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.