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.
Co-authors Maximilan Fickert and Andreas Karrenbauer