Content deleted Content added
Fixed bug in "Connection to successive shortest paths" C++ example code, the same as in O(n^3) example fixed before. |
→top: move sentence about jacobi discovery |
||
Line 1:
{{Short description|Polynomial-time algorithm for the assignment problem}}
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
[[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> 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]].
==The problem==
| |||