An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations

Tuesday, October 1, 2013 - 4:00pm to 5:00pm
Reception to follow.
Jonathan Kelner (MIT)
BIOGRAPHY Jonathan Kelner is an Associate Professor of Applied Mathematics in the MIT Department of Mathematics and a member of the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). His research focuses on the application of techniques from pure mathematics to the solution of fundamental problems in algorithms and complexity theory. He was an undergraduate at Harvard University, and he received his Ph.D. in Computer Science from MIT in 2006. Before joining the MIT faculty, he spent a year as a member of the Institute for Advanced Study. He has received a variety of awards for his work, including an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, the Best Paper Awards at SIGMETRICS 2011 and STOC 2011, the Harold E. Edgerton Faculty Achievement Award, and the MIT School of Science Teaching Prize.

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to provide asymptotically faster algorithms for the maximum s-t flow and maximum concurrent multicommodity flow problems. For graphs with n vertices and m edges, it allows us to find an ε-approximate maximum s-t flow in time O(m^{1+o(1)} ε^{-2}), improving on the previous best bound of Õ(mn^{1/3}poly(1/ε)). Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with k commodities in O(m^{1+o(1)}ε^{-2}k^2) time, improving on the existing bound of Õ(m^{4/3} poly(k,1/ε).

In describing these algorithms, I will discuss several new technical tools that may be of independent interest:

* a non-Euclidean generalization of gradient descent, bounds on its performance, and a way to use this to reduce approximate maximum flow and maximum concurrent flow to oblivious routing;

* the definition and efficient construction of a new type of flow sparsifier that ameliorates the longstanding gap between the algorithmic efficacy of sparsification on flow and cut problems; and

* the first almost-linear-time construction of an O(m^{o(1)})-competitive oblivious routing scheme.

This is joint work with Lorenzo Orecchia, Aaron Sidford, and Yin Tat Lee.