On the computational behavior of a polynomial-time network flow algorithm (Q1190598)

A variation on the Edmonds-Karp scaling approach to the minimum cost network flow problem is examined. This algorithm, which scales costs rather than right-hand sides, also runs in polynomial time. Large-scale computational experiments indicate that the computational behaviour of this scaling algorithms is much better than had been presumed.