A Faster Strongly Polynomial Minimum Cost Flow Algorithm
Operations Research · 1993 · Volume 41 · Issue 2
Abstract
In this paper, we present a new strongly polynomial time 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 O ( n log n ) shortest path problems on 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 log n ( m + n log n )) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial time algorithm, due to Z. Galil and E. Tardos, by a factor of n 2 / 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 much less than m . In this case, the running time of the algorithm is O (( m ′ + n ) log n ( m + n log n )).
Keywords
networks/graphs, flow algorithms: a faster strongly polynomial minimum cost flow algorithm
Enable JavaScript for citation tools and additional paper interactions.