Abstract

In this talk, I will describe a framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to find approximately maximum s-t flows in almost-linear time, improving on the best previous bound of Õ(mn^{1/3}).

In describing the algorithm, I will discuss several 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 framework is quite flexible, and it readily generalizes to a broader range of graph problems. If time permits, I will briefly discuss how it can be applied, without any substantial modification, to obtain similar speedups for multicommodity flow problems as well.

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

Video Recording