Hungarian algorithm: Difference between revisions

Revision as of 16:47, 12 July 2006

Revision as of 15:01, 13 July 2006

Line 1:

The '''Hungarian algorithm''' is a [[Optimization (mathematics)|combinatorial optimization]] [[algorithm]] which solves [[assignment problem]]s in [[polynomial<math>O(n^3)</math> time]]. The first version, known as the '''Hungarian method''', was invented and published by [[Harold Kuhn]] in 1955. This was revised by [[James Munkres]] in 1957, and has been known since as the '''Hungarian algorithm''', the '''Munkres assignment algorithm''', or the '''Kuhn-Munkres algorithm'''.

The algorithm developed by Kuhn was largely based on the earlier works of two other [[Hungary|Hungarian]] mathematicians: [[Dénes König]] and [[Jenő Egerváry]]. The great advantage of Kuhn’s method is that it is strongly [[polynomial]] (see [[Computational complexity theory]] for details). The main idea of the algorithm is that it combines two separate parts in Egerváry’s proof into one.