A faster strongly polynomial minimum cost flow algorithm

We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of Ο(n log n) shortest path problems on networks with n nodes and m arcs and runs in Ο(n log n(m + n log n)) steps. Using a standard transformation, this approach yields an Ο(m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial algorithm due to Galil and Tardos, by a factor of m/n. Our algorithm is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the number of shortest path problems solved is Ο((m + n) log n).