Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems

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. 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. 1. Introduction Consider the problem of computing a maximum s-t flow in a graph with unit edge capacities. While there are many different algorithms known for this problem we discuss one which views the problem purely as one of packing s-t paths so that constraints imposed by edge-capacities are not violated. The algorithm associates a length with each edge and at any step it routes a unit flow along the shortest s-t path. It then multiplies the length of every edge on this path by 1 + ffl for ..