Approximate minimum-cost multicommodity flows in $$ ilde O$$ (ɛ−2KNM) timetime
Approximate minimum-cost multicommodity flows in
$$ ilde O$$
(ɛ−2KNM) timetime
复制标题
近似最低成本多种商品流量
DOI：
--
复制
发表时间：
1996
影响因子：
2.7
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
M. Grigoriadis;L. Khachiyan
本文证明了在人工M弧网络G上，费用受限的K商品流问题的ε近似解可以通过逐次求解同一网络上的O(K(ɛ−2+logGK)logGM log(Gɛ−1GK))单商品最小费用流问题来计算。具体地说，近似的最小成本的多种商品流动可以计算在
$$ilde O$$
(Gɛ−2GKNM)运行时间，其中符号“(·)表示”直到对数因数“。这一结果将Grigoriadis和Khchiyan[4]提到的时间界限改进了Fm/N的一个因子，以及Karger和Plotkin[8]最近发展的时间界限改进了ɛ−的一个因子1。我们还提供了一个简单的
$$ilde O$$
单商品预算约束最小费用流的(NM)-时间算法
$$ilde O$$
(ɛ−3)比后一篇论文中提出的算法快了一倍。
AbstractWe show that an ε-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(ɛ−2+logGK) logGM log (Gɛ−1GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in
$$ ilde O$$
(Gɛ−2GKNM) running time, where the notation Õ(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor ofɛ−1. We also provide a simple
$$ ilde O$$
(NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is
$$ ilde O$$
(ɛ−3) times faster than the algorithm developed in the latter paper.