Content deleted Content added
restoring head |
mNo edit summary |
||
Line 1:
In [[graph theory]], the '''Hungarian algorithm''' is an [[algorithm]] on [[Optimization|Combinatorial Optimization]], which solves instances of the [[assignment problem]] in [[polynomial time]]. Its first version, known as the '''Hungarian method''', was invented and published by [[Harold Kuhn]] in 1955. The Hungarian method was in turn revised by [[James Munkres]] in 1957, and ever since it has been widely known as the '''Hungarian algorithm''', or the '''Munkres' assignment algorithm''', or even as the '''Kuhn-Munkres algorithm'''.
==Theory==
The algorithm developped by Kuhn was largerly based on the earlier works of two other [[Hungarian]] mathematicians: [[Konig]] and [[Egervary]]. The great advantage of Kuhn’s method is that it is strongly polynomial. The main idea of the algorithm is that it combines two separate parts in Egervery’s proof (computing a deficient set and revising the current <math>\pi</math> ) into one.
==Modelisation==
| |||