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.
http://i.stanford.edu/pub/cstr/reports/cs/tn/95/19/CS-TN-95-19.pdf