Institution: Stanford University, Department of Computer Science

Title: Fast approximation algorithms for multicommodity flow problems

Author: Leighton, Tom

Author: Makedon, Fillia

Author: Plotkin, Serge

Author: Stein, Clifford

Author: Tardos, Eva

Author: Tragoudas, Spyros

Date: August 1991

Abstract: In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. Our algorithms are significantly faster than the best previously known algorithms, that were based on linear programming. For a k-commodity multicommodity flow problem, the running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. Given any multicommodity flow problem as input, our algorithm is guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + epsilon)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in the "sparsest cut" problems and the uniform concurrent flow problems if k <= the square root of m.

http://i.stanford.edu/pub/cstr/reports/cs/tr/91/1375/CS-TR-91-1375.pdf