Hungarian algorithm: Difference between revisions

Revision as of 02:47, 29 January 2006

Revision as of 02:48, 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.

===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 [[GuassianGaussian 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.

===External links===

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

[[Category:Algorithms]]