Hungarian algorithm: Difference between revisions

Revision as of 10:26, 12 March 2025

Revision as of 00:11, 28 March 2025

Line 2:

The '''Hungarian method''' is a [[combinatorial optimization]] [[algorithm]] that solves the [[assignment problem]] in [[polynomial time]] and which anticipated later [[Duality (optimization)|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]].<ref name="kuhn1955">Harold W. Kuhn, "The Hungarian Method for the assignment problem", ''[[Naval Research Logistics Quarterly]]'', '''2''': 83–97, 1955. Kuhn's original publication.</ref><ref name="kuhn1956">Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", ''Naval Research Logistics Quarterly'', '''3''': 253–258, 1956.</ref> 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.<ref>{{Cite web|url=http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm|archive-url = https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm|archive-date = 16 October 2015|title = Presentation}}</ref>

[[James Munkres]] reviewed the algorithm in 1957 and observed that it is [[Time complexity#Strongly and weakly -polynomial time|(strongly) polynomial]].<ref name="munkres">J. Munkres, "Algorithms for the Assignment and Transportation Problems", ''[[Journal of the Society for Industrial and Applied Mathematics]]'', '''5'''(1):32–38, 1957 March.</ref> Since then the algorithm has been known also as the '''Kuhn–Munkres algorithm''' or '''Munkres assignment algorithm'''. The [[Computational complexity theory#Time and space complexity|time complexity]] of the original algorithm was <math>O(n^4)</math>, however [[Jack Edmonds|Edmonds]] and [[Richard Karp|Karp]], and independently Tomizawa, noticed that it can be modified to achieve an <math>O(n^3)</math> running time.<ref>{{Cite journal|last1=Edmonds|first1=Jack|last2=Karp|first2=Richard M.|date=1972-04-01|title=Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems|journal=Journal of the ACM|volume=19|issue=2|pages=248–264|language=EN|doi=10.1145/321694.321699|s2cid=6375478|doi-access=free}}</ref><ref>{{Cite journal|last=Tomizawa|first=N.|date=1971|title=On some techniques useful for solution of transportation network problems|journal=Networks|language=en|volume=1|issue=2|pages=173–194|doi=10.1002/net.3230010206|issn=1097-0037}}</ref> [[L. R. Ford, Jr.|Ford]] and [[D. R. Fulkerson|Fulkerson]] extended the method to general maximum flow problems in form of the [[Ford–Fulkerson algorithm]].

==The problem==