Accession Number : ADA254048


Title :   Fast Approximation Algorithms for Multicommodity Flow Problems


Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Leighton, Tom ; Makedon, Fillia ; Plotkin, Serge ; Stein, Clifford ; Tardos, Eva ; Tragoudas, Spyros


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254048.pdf


Report Date : Aug 1991


Pagination or Media Count : 27


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 iii 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 + e)-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 or - m.


Descriptors :   *ALGORITHMS , *COMBINATORIAL ANALYSIS , *NETWORK FLOWS , INPUT , COMPUTATIONS , THEORY , COMPUTER PROGRAMMING , LINEAR PROGRAMMING , COMMODITIES , UNIFORMS , PAPER , STRUCTURES , ISOLATION , TIME , POLYNOMIALS , MATHEMATICS , FLOW


Subject Categories : Numerical Mathematics
      Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE