We present a novel algorithm for the min-cost flow problem that is competitive with recent third-party implementations of well-known algorithms for this problem and even outperforms them on certain realistic instances. We formally prove correctness of our algorithm and show that the worst-case running time is in O(‖b‖_1(m + n log n)) where b is the vector of demands. Combined with standard scaling techniques, this pseudo-polynomial bound can be made polynomial in a straightforward way. Furthermore, we evaluate our approach experimentally. Our empirical findings indeed suggest that the running time does not significantly depend on the costs and that a linear dependence on ‖b‖_1 is overly pessimistic.
展开▼
机译：我们提出了一种新的算法，用于最小的成本流动问题，这是对这个问题的众所周知算法的最近第三方实现竞争，甚至在某些现实实例上表现出差异。我们正式证明了我们的算法的正确性，并显示了最坏情况的运行时间在O（‖b‖_1（m + n log n）中），其中b是需求的向量。结合标准缩放技术，该伪多项式结合可以以直接的方式制造多项式。此外，我们通过实验评估我们的方法。我们的经验调查结果确实表明，运行时间没有显着取决于成本，并且对‖b‖_1的线性依赖性过于悲观。
展开▼
