|
The algorithm developed by Kuhn was largely based on the earlier works of two other [[Hungarian]] mathematicians: [[Denes Kőnig]] and [[Jenő Egerváry]]. 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 π) into one. The procedure of covering the prime zeros can be implemented in a [[flow network]], and automated by means of the [[Ford-Fulkerson algorithm]]. The ''n''×''m'' matrix is transformed in a <math>G=(U,V)</math> bipartite graph, with I/O capacity equal to 1. Each arc joining the nodes of the flow network represents a zero in the cost matrix. After the maximum flow is obtained, the affected arcs represent the prime zeros. The [[minimum cut]] obtained by Ford-Fulkerson automates the process of covering the independent zeros. Each node that gets "cut" on the max-flow graph represents a covered row or line on the cost matrix. However, in the Hungarian method, the assignment can be easily found on the cost matrix, yet the expansion into a max-flow sub-problem is a useful method in more complex scenarios.
==ModelisationModeling==
The algorithm models an assignment problem as a ''n''×''m'' cost matrix, where each element represents the cost of assigning the ''n''th worker to the ''m''th job. By default, the algorithm performs minimization on the elements of the matrix; hence in the case of a price-minimization problem, it is sufficient to begin [[Gaussian elimination]] to make zeros appear (at least one zero per line and per column). However, in the case of a profit-maximization problem, the cost matrix needs to be modified so that minimization of its elements results in maximizing the original cost values. In an infinite-cost problem, the initial cost matrix can be re-modelled by subtracting every element of each line from the maximum value of the element that line (or column respectively). In a finite-cost problem, all the elements are subtracted from the maximum value of the whole matrix.
==Algorithm [http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html]==
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 [[Gaussian elimination]] step 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.
:'''Step 0''': Create an ''n''×''m'' cost matrix in which each element represents the cost of assigning the ''n''th worker to the ''m''th job. Rotate the matrix so that there are at least as many rows as columns and let k=min(n,m).
:'''Step 1''': For each row of the matrix, find the smallest element and subtract it from every element in its row. Go to Step 2.
:'''Step 2''': Find a zero (Z) in the resulting matrix. If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3.
:'''Step 3''': Cover each column containing a starred zero. If K columns are covered, the starred zeros describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go to Step 4.
:'''Step 4''': Find a noncovered zero and prime it. If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6.
:'''Step 5''': Construct a series of alternating primed and starred zeros as follows. Let Z0 represent the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until the series terminates at a primed zero that has no starred zero in its column. Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix. Return to Step 3.
:'''Step 6''': Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column. Return to Step 4 without altering any stars, primes, or covered lines.
:'''DONE''': Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j.
==A minimization problem==
| 