BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-91-1375
       ENTRY:: September 02, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Fast approximation algorithms for multicommodity flow
               problems
        TYPE:: Technical Report
      AUTHOR:: Leighton, Tom
      AUTHOR:: Makedon, Fillia
      AUTHOR:: Plotkin, Serge
      AUTHOR:: Stein, Clifford
      AUTHOR:: Tardos, Eva
      AUTHOR:: Tragoudas, Spyros
        DATE:: August 1991
       PAGES:: 28
    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.
       NOTES:: [Adminitrivia V1/RAM/19940902]
         END:: STAN//CS-TR-91-1375