The Scaling Network Simplex Algorithm

Ravindra K. Ahuja and James B. Orlin
Additional contact information
Ravindra K. Ahuja: Indian Institute of Technology, Kanpur, India
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1992, vol. 40, issue 1-supplement-1, S5-S13

Abstract: In this paper, we present a new primal simplex pivot rule and analyze the worst case complexity of the resulting simplex algorithm for the minimum cost flow, the assignment, and the shortest path problems. We consider networks with n nodes, m arcs, integral arc capacities bounded by an integer number U , and integral arc costs whose magnitudes are bounded by an integer number C . Our pivot rule may be regarded as a scaling version of Dantzig's pivot rule. Our pivot rule defines a threshold value Δ, which is initially at most 2 C , and the rule permits any arc with a violation of at least Δ/2 to be the editing variable. We select the leaving arc so that strong feasibility of the basis is maintained. When there is no arc satisfying this rule, then we replace Δ by Δ/2 and repeat the process. The algorithm terminates when Δ O ( nmU log C ) pivots and can be implemented to run in O ( m 2 U log C ) time. Specializing these results for the assignment and shortest path problems we show that the simplex algorithm solves these problems in O ( n 2 log C ) pivots and O ( nm log C ) time.

Keywords: networks/graphs:; improved; simplex; algorithms; for; network; flow; problems (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S5 (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:40:y:1992:i:1-supplement-1:p:s5-s13

Access Statistics for this article

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