A novel dual ascent algorithm for solving the min-cost flow problem

We present a novel alg orithm 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 0(||β||i(m + ηlogη)) 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 ||β||i is overly pessimistic.