Content deleted Content added
max changed to min. In case of an NxM matrix, the maximum number of matchings (n) is min(number of people, number of assignments) |
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | Suggested by BrownHairedGirl | Linked from User:BrownHairedGirl/Articles_with_bare_links | #UCB_webform_linked 821/2197 |
||
Line 1:
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 the name "Hungarian method" because the algorithm was largely based on the earlier works of two [[Hungary|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>
[[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}}</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>{{how|date=November 2019|title=What kind of change is needed?}} One of the most popular{{Citation needed|date=November 2019}} <math>O(n^3)</math> variants is the Jonker–Volgenant algorithm.<ref name="JVAlg">{{cite journal |last1=Jonker |first1=R. |last2=Volgenant |first2=A. |title=A shortest augmenting path algorithm for dense and sparse linear assignment problems |journal=Computing |date=December 1987 |volume=38 |issue=4 |pages=325–340 |doi=10.1007/BF02278710|s2cid=7806079 }}</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]]. 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>https://web.archive.org/web/20151016182619/http://www.lix.polytechnique.fr/~ollivier/JACOBI/presentationlEngl.htm</ref>
==The problem==
| |||