Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Faster and simpler algorithms for multicommodity flow and other fractional packing problems

Garg, Naveen and Könemann, Jochen

MPI-I-97-1-025. November 1997, 13 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
This paper considers the problem of designing fast, approximate,
combinatorial algorithms for multicommodity flows and other fractional
packing problems. We provide a different approach to these problems
which yields faster and much simpler algorithms. In particular we
provide the first polynomial-time, combinatorial approximation algorithm
the fractional packing problem; in fact the running time of our
algorithm is
strongly polynomial. Our approach also allows us to substitute
shortest path computations for min-cost flow computations in computing
maximum concurrent flow and min-cost multicommodity flow; this yields
faster algorithms when the number of commodities is large.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-025.ps167 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Garg, Naveen and K{\"o}nemann, Jochen},
  TITLE = {Faster and simpler algorithms for multicommodity flow and other fractional packing problems},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-025},
  MONTH = {November},
  YEAR = {1997},
  ISSN = {0946-011X},