The Hungarian or Munkres algorithm is a method for solving the asignment problem: Given workers and tasks, and an 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 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 [[1]] A description of serial and parallel implementations.