TY - JOUR
TI - Approximate minimum-cost multicommodity flows in Õ(_{Ɛ}^{-2}KNM) time
DO - https://doi.org/doi:10.7282/t3-agzc-6w07
AU - Grigoriadis, Michael D.
AU - Khachiyan, Leonid
PY - 1995-05
AB - 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).
KW - Approximation algorithm
KW - Block-angular program
KW - Minimum-cost multicommodity network flow
KW - Structured optimization
LA - English
ER -