English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

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

MPS-Authors
/persons/resource/persons44477

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

/persons/resource/persons44808

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-97-1-025.pdf
(Any fulltext), 222KB

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-97-1-025). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://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.