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

ABSTRACT
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.