Abstract
Efficient algorithms based upon Balinski's signature method are described for solving then × n assignment problem. These algorithms are special variants of the dual simplex method and are shown to have computational bounds of O(n 3). Variants for solving sparse assignment problems withm arcs that require O(m) space and O(mn + n 2 logn) time in the worst case are also presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A.V. Aho, J.E. Hopcroft and J.D. Ullman,The design and analysis of computer algorithms (Addison-Wesley, Reading, MA, 1974).
M.L. Balinski, “Signature methods for the assignment problem”, to appear inOperations Research.
M.L. Balinski and R.E. Gomory, “A primal method for the assignment and transportation problems”,Management Science 10 (1964) 578–593.
R. Barr, F. Glover and D. Klingman, “The alternating path basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1–13.
D. Bertsekas, “A new algorithm for the assignment problem”,Mathematical Programming 21 (1981) 152–171.
W.H. Cunningham, “A network simplex method”,Mathematical Programming 11 (1976) 105–116.
W.H. Cunningham and A.B. Marsh, III, “A primal algorithm for optimum matching”,Mathematical Programming Study 8 (1978) 50–72.
G.B. Dantzig, “Application of the Simplex Method to a Transportation Problem”, in: T.C. Koopmans, ed.,Activity analysis of production and allocation (Wiley, New York, 1951) pp. 359–373.
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.
M.L. Fredman, J. Komlós and E. Szemerédi, “Storing a sparse table with O(1) worst case access time”,Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (1982), 165–169.
M.L. Fredman and R.E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, preprint, January, 1984.
Z. Galil, S. Micali and H. Gabow, “Maximal weighted matching on general graphs”,Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (1982), 255–261.
J.E. Hopcraft and R.M. Karp, “An 5/2 Algorithm for maximum matchings in bipartite graphs”,SIAM Journal on Computing 2 (1973) 225–231.
M.S. Hung, “A polynomial simplex method for the assignment problem”,Operations Research 31 (1983) 595–600.
M.S. Hung and W.O. Rom, “Solving the assignment problem by relaxation”,Operations Research 28 (1980) 969–982.
H.W. Kuhn, “The Hungarian method for the assignment problem”,Naval Research Logistics Quarterly 2 (1955) 83–97.
E. Lawler,Combinatorial optimization, networks and matroids (Holt, Rinehart and Winston, New York, 1976).
E. Roohy-Laleh,Improvements to the theoretical efficiency of the network simplex method, Ph.D. Thesis, Carleton University (Ottawa, 1981).
D.D. Sleator and R.E. Tarjan, “Self-adjusting heaps”,SIAM Journal on Computing, submitted.
R.E. Tarjan, “Amortized computational complexity”,SIAM Journal on Algebraic and Discrete Methods, to appear.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant No. MCS-8006064 and by the Army Research Office under Contracts No. DAAG 29-82-K0163 and DAAG 29-83-K0106
Rights and permissions
About this article
Cite this article
Goldfarb, D. Efficient dual simplex algorithms for the assignment problem. Mathematical Programming 33, 187–203 (1985). https://doi.org/10.1007/BF01582245
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582245