A faster strongly polynomial minimum cost flow algorithm
A faster strongly polynomial minimum cost flow algorithm
复制标题
DOI：
10.1145/62212.62249
复制
发表时间：
1993-04
期刊：
影响因子：
--
通讯作者：
J. Orlin
中科院分区：
文献类型：
--
作者：
J. Orlin
我们提出了一个新的强多项式算法的最小费用流问题的基础上，改进的Edmonds-Karp缩放技术。我们的算法解决了无容量限制的最小费用流问题作为一个序列的（n log n）最短路径问题的网络上有n个节点和m个弧，运行在（n log n（m + n log n））的步骤。使用一个标准的转换，这种方法产生一个（m log n（m + n log n））算法的容量限制的最小费用流问题。该算法将Galil和Tardos提出的最佳强多项式算法改进了m/n倍。如果具有有限上界的弧的数目，比如说m '，远小于m，我们的算法甚至更有效。在这种情况下，解决的最短路径问题的数量是（（m + n）log n）。
We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of &Ogr;(n log n) shortest path problems on networks with n nodes and m arcs and runs in &Ogr;(n log n(m + n log n)) steps. Using a standard transformation, this approach yields an &Ogr;(m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial algorithm due to Galil and Tardos, by a factor of m/n. Our algorithm is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the number of shortest path problems solved is &Ogr;((m + n) log n).