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
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.
Acknowledgement:
References to related material:
To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
---|---|
167 KBytes | |
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |