Report Number: CS-TR-91-1375
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