The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave it the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry.[1][2] However, in 2006 it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin.[3]
James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.[4] Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm. The time complexity of the original algorithm was , however Edmonds and Karp, and independently Tomizawa, noticed that it can be modified to achieve an running time.[5][6] Ford and Fulkerson extended the method to general maximum flow problems in form of the Ford–Fulkerson algorithm.
- ^ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
- ^ Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.
- ^ "Presentation". Archived from the original on 16 October 2015.
- ^ J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.
- ^ Edmonds, Jack; Karp, Richard M. (1 April 1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems". Journal of the ACM. 19 (2): 248–264. doi:10.1145/321694.321699. S2CID 6375478.
- ^ Tomizawa, N. (1971). "On some techniques useful for solution of transportation network problems". Networks. 1 (2): 173–194. doi:10.1002/net.3230010206. ISSN 1097-0037.