Hungarian algorithm: Difference between revisions

Revision as of 23:29, 29 June 2006

Revision as of 08:45, 3 July 2006

Line 1:

The '''Hungarian algorithm''' is a [[Optimization (mathematics)|combinatorial optimization]] [[algorithm]] which solves [[assignment problem]]s in [[polynomial 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: [[DenesDé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 Egervery’sEgerváry’s proof into one.

==Modeling==