Approximating Fractional Multicommodity Flow Independent of the Number of Commodities

Abstract

We describe fully polynomial time approximation schemes for various multicommodity flow problems in graphs with m edges and n vertices. We present the first approximation scheme for maximum multicommodity flow that is independent of the number of commodities k, and our algorithm improves upon the run time of previous algorithms by this factor of k, running in ${{\cal O}^*(\epsilon^{-2}m^2)}$ time. For maximum concurrent flow and minimum cost concurrent flow, we present algorithms that are faster than the current known algorithms when the graph is sparse or the number of commodities k is large, i.e., k > m/n. Our algorithms build on the framework proposed by Garg and Könemann [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1998, pp. 300--309]. They are simple, deterministic, and for the versions without costs, they are strongly polynomial. The approximation guarantees are obtained by comparison with dual feasible solutions found by our algorithm. Our maximum multicommodity flow algorithm extends to an approximation scheme for the maximum weighted multicommodity flow, which is faster than those implied by previous algorithms by a factor of k/log W, where W is the maximum weight of a commodity.