A Faster Strongly Polynomial Minimum Cost Flow Algorithm

James B. Orlin
Additional contact information
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1993, vol. 41, issue 2, 338-350

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 (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.2.338 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:2:p:338-350

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().