de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44477

Garg,  Naveen
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44808

Könemann,  Jochen
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

1997-1-025
(Any fulltext), 10KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Garg, N., & Könemann, J.(1997). Faster and simpler algorithms for multicommodity flow and other fractional packing problems (MPI-I-1997-1-025). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9CD9-B
Abstract
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.