A new scaling algorithm for the minimum cost network flow problem

In this paper, we present a new polynomial time algorithm for solving the minimum cost network flow problem. This algorithm is based on Edmonds–Karp's capacity scaling and Orlin's excess scaling algorithms. Unlike these algorithms, our algorithm works directly with the given data and original network, and dynamically adjusts the scaling factor between scaling phases, so that it performs at least one flow augmentation in each phase. Our algorithm has a complexity of O(m(m+n log n) log (B/(m+n))), where n is the number of nodes, m is the number of arcs, and B is the sum of the finite arc capacities and supplies in the network.