A competitive (dual) simplex method for the assignment problem. (English) Zbl 0596.90064

The worst case complexity of the simplex method is known to be exponential for general liner programming problems. For the linear assignment problem the author presents new pivot choice rules, and shows that the worst case complexity of the dual simplex method reduces to \(\left( \begin{matrix} n-1\\ 2\end{matrix} \right)\) pivots and \(0(n^ 3)\) time, when these rules are applied (n denotes the number of assignments). It is argued that the average number of pivots is at most n log n.
Reviewer: M.Bastian


90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] M.L. Balinski, ”Signature methods for the assignment problem”,Operations Research 33 (1985) 527–537. · Zbl 0583.90064
[2] M.L. Balinski, ”Signatures des points extrêmes du polyhèdres dual du problème de transport”,Comptes Rendus de l’Académie des Sciences de Paris 296 (1983), Série I, 456–459. · Zbl 0527.90069
[3] M.L. Balinski, ”The Hirsch conjecture for dual transportation polyhedra”,Mathematics of Operations Research 9 (1984) 629–633. · Zbl 0555.90071
[4] M.L. Balinski and Andrew Russakoff, ”Faces of dual transportation polyhedra”,Mathematical Programming Study 22 (1984) 1–8. · Zbl 0553.90066
[5] R. Barr, F. Glover and D. Klingman, ”The alternating path basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1–13. · Zbl 0378.90097
[6] W.H. Cunningham, ”A network simplex method”,Mathematical Programming 11 (1976) 105–116. · Zbl 0352.90039
[7] W.H. Cunningham, ”Theoretical properties of the network simplex method”,Mathematics of Operations Research 4 (1979) 196–208. · Zbl 0412.90068
[8] J. Edmonds and R.M. Karp, ”Theoretical improvements in algorithmic efficiency for network flow problems”,Journal of the Association for Computing Machinery 19 (1972) 248–264. · Zbl 0318.90024
[9] Donald Goldfarb, ”Efficient dual simplex methods for the assignment problem”,Mathematical Programming 33 (1985) 187–203. · Zbl 0578.90051
[10] Ming S. Hung, ”A polynomial simplex method for the assignment problem”,Operations Research 31 (1983) 595–600. · Zbl 0519.90056
[11] James Orlin, ”On the simplex algorithm for networks and generalized networks”, to appear inMathematical Prógramming. · Zbl 0592.90031
[12] E. Roohy-Laleh, ”Improvements to the theoretical efficiency of the network simplex method”, Ph.D. Thesis, Carleton University, 1981.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.