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

Abstract

This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We present new, faster, and much simpler algorithms for these problems.