Theory Seminar

  • Ph.D. Student, Theory of Computation
  • Computer Science and Artificial Intelligence Laboratory (CSAIL)
  • Massachusetts Institute of Technology

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

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs and I will show how to use this framework to achieve faster asymptotic running times for solving the maximum s-t flow and maximum concurrent multicommodity flow problems. For graphs with n vertices and m edges, I will present an algorithm for computing an epsilon-approximate maximum s-t flow in time O(m^{1+o(1)} epsilon^{-2}), improving on the previous best bound of \tilde{O}(mn^{1/3}poly(1/epsilon)), and I will discuss how to compute an epsilon-approximate maximum concurrent multicommodity flow problem with k commodities in O(m^{1+o(1)}epsilon^{-2}k^2) time, improving on the existing bound of \tilde{O}(m^{4/3} poly(k,1/epsilon).

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 Jonathan Kelner, Lorenzo Orecchia, and Yin Tat Lee.

For More Information, Please Contact: