MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys

MPI-I-97-1-025

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

Garg, Naveen and Könemann, Jochen

November 1997, 13 pages.

.
Status: available - back from printing

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 for 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 much faster algorithms when the number of commodities is large.

  • MPI-I-97-1-025.ps
  • Attachement: ATTTWPPM (167 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-025

Hide details for BibTeXBibTeX
@TECHREPORT{GargKoenemann97,
  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},
}