Abstract
“Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling.” - Sir John (from Michael Innes,The Open House (A Sir John Appleby Mystery), Penguin Books, 1974).
A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asx ij < 0. A choice (i,j) over columnsj having at least 3 basic activities that minimizesx ij is shown to converge in at most ( n-12 ) pivots, and at most O(n 3) time, and it is argued that on average the number of pivots is at mostn logn.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.L. Balinski, “Signature methods for the assignment problem“,Operations Research 33 (1985) 527–537.
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.
M.L. Balinski, “The Hirsch conjecture for dual transportation polyhedra“,Mathematics of Operations Research 9 (1984) 629–633.
M.L. Balinski and Andrew Russakoff, “Faces of dual transportation polyhedra“,Mathematical Programming Study 22 (1984) 1–8.
R. Barr, F. Glover and D. Klingman, “The alternating path basis algorithm for assignment problems“,Mathematical Programming 13 (1977) 1–13.
W.H. Cunningham, “A network simplex method“,Mathematical Programming 11 (1976) 105–116.
W.H. Cunningham, “Theoretical properties of the network simplex method“,Mathematics of Operations Research 4 (1979) 196–208.
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.
Donald Goldfarb, “Efficient dual simplex methods for the assignment problem“,Mathematical Programming 33 (1985) 187–203.
Ming S. Hung, “A polynomial simplex method for the assignment problem“,Operations Research 31 (1983) 595–600.
James Orlin, “On the simplex algorithm for networks and generalized networks”, to appear inMathematical Prógramming.
E. Roohy-Laleh, “Improvements to the theoretical efficiency of the network simplex method”, Ph.D. Thesis, Carleton University, 1981.
Author information
Authors and Affiliations
Additional information
Dedicated with affection to George B. Dantzig on the occasion of his seventieth birthday.
Rights and permissions
About this article
Cite this article
Balinski, M.L. A competitive (dual) simplex method for the assignment problem. Mathematical Programming 34, 125–141 (1986). https://doi.org/10.1007/BF01580579
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580579