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
MSC:
| 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 |
Keywords:
signature;worst case complexity;simplex method;linear assignment;new pivot choice rules;dual simplex method;average number of pivotsCite
Full Text:DOI
References:
| [1] | M.L. Balinski, ”Signature methods for the assignment problem”,Operations Research 33 (1985) 527–537. ·Zbl 0583.90064 ·doi:10.1287/opre.33.3.527 |
| [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 ·doi:10.1287/moor.9.4.629 |
| [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 ·doi:10.1007/BF01584319 |
| [6] | W.H. Cunningham, ”A network simplex method”,Mathematical Programming 11 (1976) 105–116. ·Zbl 0352.90039 ·doi:10.1007/BF01580379 |
| [7] | W.H. Cunningham, ”Theoretical properties of the network simplex method”,Mathematics of Operations Research 4 (1979) 196–208. ·Zbl 0412.90068 ·doi:10.1287/moor.4.2.196 |
| [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 ·doi:10.1007/BF01582245 |
| [10] | Ming S. Hung, ”A polynomial simplex method for the assignment problem”,Operations Research 31 (1983) 595–600. ·Zbl 0519.90056 ·doi:10.1287/opre.31.3.595 |
| [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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
