Fast Approximation Algorithm for Minimum Cost Multicommodity Flow

Minimum-cost multicommodity flow problem is one of the classical optimization problems that arises in a variety of contexts. Applications range from finding optimal ways to route information through communication networks to VLSI layout. In this paper, we describe an efficient deterministic approximation algorithm, which given that there exists a multicommodity flow of cost B that satisfies all the demands, produces a flow of cost at most (1+ ffi )B that satisfies (1 \Gamma ffl)-fraction of each demand. For constant ffi and ffl, our algorithm runs in O (kmn 2 ) time, which is an improvement over the previously fastest (deterministic) approximation algorithm for this problem due to Plotkin, Shmoys, and Tardos, that runs in O (k 2 m 2 ) time. 1 Introduction The multicommodity flow problem involves simultaneously shipping several different commodities from their respective sources to their sinks in a single network so that the total amount of flow going through each edge is..