Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
We combine the work of Garg and Konemann, and Fleischer with ideas from dynamic graph algorithms to obtain faster (1 e) approximation schemes for various versions of the multicommodity flow problem. In particular, if e 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 O(mn) flow decomposition barrier for single commodity flow.
STOC '10