This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity ows and other fractional packing problems. We provide a di erent approach to these problems which yields faster and much simpler algorithms. In particular we provide the rst 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 ow computations in computing maximum concurrent ow and min-cost multicommodity ow; this yields much faster algorithms when the number of commodities is large.
Using the Garg-Könemann approximation algorithm REF , they provide a (1+ )(1+2lnn) approximation of the problem, where n is the number of sensors.
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science