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