Approximate minimum-cost multicommodity flows in Õ(_Ɛ^-2KNM) time

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 $O(K(eps^{-2}+log K)log Mlog(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 $ilde O(eps^{-2}KNM)$ running time, where the notation $ilde O(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 $ilde O(NM)$-time algorithm for single-commodity budget-constrained minimum-cost flows which is $ilde O(eps^{-3})$ times faster than the algorithm of Karger and Plotkin (1995).Technical report LCSR-TR-24