Hungarian algorithm: Difference between revisions

Revision as of 19:41, 2 January 2006

Revision as of 02:47, 29 January 2006

Line 1:

The '''Hungarian''' or '''Munkres''' algorithm is a method for solving the asignment problem: Given <math>n</math> workers and tasks, and an <math>N x N</math> matrix containing the cost of assigning each worker to a task, find the cost minimizing assigment. The algorithm works in polynomial time.

In [[graph theory]], the '''Hungarian algorithm''' is an [[algorithm]] on [[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'''.

===The Algorithm===

The algorithm works by increasing the number of zeros in the matrix and searching for a set of starred zeros, one in every row and column. Zeros are primed, starred, or neither during the algorithm. If there are insufficent zeros a quick [[Guassian elimination]] adds more. If there are not enough starred zeros, the primed zeros are starred and the starred zeros primed. Primed zeros are zeros in a column without any more zeros, which, because they are in the same row as another zero were not starred.

===External links

[[http://www.netlib.org/utk/lsi/pcwLSI/text/node220.html]] A description of serial and parallel implementations.

[[Category:Algorithms]]

[[Category:Graph theory]]