**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(m*^{4/3})\p(1/\e) and *\e*-approximately minimum *s*-*t* cuts in time *\o(m+n*^{4/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(m*^{4/3}\p(k,\e^{-1})).

Talk 2 of the invited session Fri.3.H 3013

**"Flows, cuts, and sparsifiers"** [...]

Cluster 2

**"Combinatorial optimization"** [...]