非表示:
キーワード:
-
要旨:
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.
