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.

http://i.stanford.edu/pub/cstr/reports/cs/tn/95/19/CS-TN-95-19.pdf