Report Number: CS-TN-95-19
Institution: Stanford University, Department of Computer Science
Title: Fast Approximation Algorithm for Minimum Cost Multicommodity Flow
Author: Kamath, Anil
Author: Palmon, Omri
Author: Plotkin, Serge
Date: March 1995
Abstract: 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+\delta)B$ that satisfies $(1-\epsilon)$-fraction of each demand. For constant $\delta$ and $\epsilon$, 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^2m^2)$ time.