Abstract
We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimensionN and reaches an order of magnitude forN equal to several hundreds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Lawler,Combinatorial optimization: networks and matroids (Holt, Rinehart and Winston, 1976).
H.W. Kuhn, “The Hungarian method for the assignment problem”,Naval Research Logistics Quarterly 2 (1955) 83–97.
R.S. Barr, F. Glover and D. Klingman, “The alternating basis algorithm for assignment problems”,Mathematical Programming 13 (1977) 1.
G.H. Bradley, G.G. Brown and G.W. Graves, ‘Design and implementation of large scale primal transhipment algorithms”,Management Science 24 (1977) 1.
R.V. Helgason and J.L. Kennigton, “NETFLOW program documentation”, technical report IEOR 76011, Department of Industrial Engineering and Operations Research, Southern Methodist University (1976).
R.S. Hatch, “Bench marks comparing transportation codes based on primal simplex and primal—dual algorithms”,Operations Research 23 (1975) 1167.
L.F. McGinnis, “Implementation and testing of a primal—dual algorithm for the assignment problem”, Industrial and Systems Engineering report series No. J-78-31, Georgia Institute of Technology (November 1978).
A. Weintraub, and F. Barahona, “A dual algorithm for the assignment problem”, Departmento de Industrias Report No. 2, Universidad de Chile-Sede Occidente (April 1979).
F. Glover and D. Klingman, “Comment on a note by Hatch on network algorithms”Operations Research 26 (1978) 370.
J. Edmonds and R. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”,Journal of the Association for Computing Machinery 19 (1972) 248–264.
D.P. Bertsekas, “An algorithm for the Hitchcock transportation problem”,Proceedings of the 18th Allerton conference on communication, control and computing, Allerton Park, 11 Oct. 1979.
M.D. Grigoriadis, Talk at Mathematical Programming Symposium, Montreal, August 1979 (also private communication).
Author information
Authors and Affiliations
Additional information
Work supported by Grant NSF ENG-7906332.
Rights and permissions
About this article
Cite this article
Bertsekas, D.P. A new algorithm for the assignment problem. Mathematical Programming 21, 152–171 (1981). https://doi.org/10.1007/BF01584237
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584237