Hungarian algorithm: Difference between revisions

Revision as of 07:21, 15 November 2021

Revision as of 23:34, 13 January 2022

Line 1:

{{short description|a combinatorial optimization algorithm that solves the assignment problem in polynomial time}}

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>