DIMACS TR: 95-13
Approximate Minimum-cost Multicommodity Flows in
$\tilde 0(\eps^{-2}KNM)$ Time
Authors: Michael D. Grigoriadis and L.G. Khachiyan
ABSTRACT
We show that an $\veps$-approximate solution of the cost-constrained
$K$-commodity flow problem on an $N$-node $M$-arc network $G$ can be
computed by sequentially solving $0(K(\eps^{-2}+\log K)\log M\log(\eps^{-1}K))$
single-commodity minimum-cost flow problems on the same network. In
particular, an approximate minimum-cost multicommodity flow can be computed
in $\tilde 0(\eps^{-2}KNM)$ running time, where the notation $\tilde 0(\cdot)
$ means ``up to logarithmic factors''. This result improves the time
bound mentioned in Grigoriadis and Khachiyan (1994) by a factor of $M/N$
and that developed recently in Karger and Plotkin (1995) by a factor of
$\eps^{-1}$. We also provide a simple $\tilde 0(NM)$-time algorithm for
single-commodity budget-constrained minimum-cost flows which is
$\tilde 0(\eps^{-3})$ times faster than the algorithm of Karger and Plotkin
(1995).
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-13.ps.gz
DIMACS Home Page