A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM

In this paper, we present a new strongly polynomial time algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-K arp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of O(n log n) shortest path problems o n networks with n nodes and m arcs and runs in O(n log n (m + n log n) ) time. Using a standard transformation, this approach yields an O(m l og n (m + n log n)) algorithm for the capacitated minimum cost flow pr oblem. This algorithm improves the best previous strongly polynomial t ime algorithm, due to Z. Galil and E. Tardos, by a factor of n2/m. Our algorithm for the capacitated minimum cost flow problem is even more efficient if the number of arcs with finite upper bounds, say m', is m uch less than m. In this case, the running time of the algorithm is O( (m' + n)log n(m + n log n)).