Algorithms and Complexity Seminar

Fast Approximation of Multicommodity Flow Problems via Dynamic Graph Algorithms

Aleksander Mądry (MIT)


We present faster (1-eps)-approximation schemes for various versions of the multicommodity flow problem. In particular, if eps is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match -- up to poly-logarithmic factors and some provably optimal terms -- the Omega(mn) flow-decomposition barrier for single-commodity flow.

Our approach is based on combining the existing Lagrangian-relaxation algorithms for these problems with ideas from dynamic graph algorithms.