 # Hungarian method

An algorithm to solve the standard assignment problem (presented by H. Kuhn in 1955). Let C be the $LaTeX: n\times n$ cost matrix.

• Step 0 (initialize). Subtract the least element of each row from that row of $LaTeX: C$. Then, do likewise for each column. The resulting matrix, $LaTeX: C^0$ has a zero in every row and column. (Further, a least cost assignment for $LaTeX: C^0$ is also a least cost assignment for $LaTeX: C$.) Re-define $LaTeX: C=C^0$.
• Step 1 (cover zeros). Draw the minimum number of lines through the rows and columns to cover all zeros in $LaTeX: C$. If that minimum is $LaTeX: n$, you can assign $LaTeX: i$ to $LaTeX: j$ such that $LaTeX: C_{ij}=0$; then you can remove row $LaTeX: i$ and column $LaTeX: j$, repeating the process to obtain an optimal assignment. Otherwise, if that minimum is greater than $LaTeX: n$, continue.
• Step 2 (revise $LaTeX: C$). Select the minimum uncovered element. Subtract this from each uncovered element and add it to each twice-covered element (i.e., to those with both a horizontal and vertical line intersecting). Return to step 1.

Example:


Job
_ 1  2  3  4  5 _
|                 |
|  1  2  3  4  7  | 1
|  7  4  2  6  5  | 2
C = |  2  4  3  1  4  | 3
|  2  3  1  2  3  | 4
|  5  4  3  2  4  | 5
|_               _|


After subtracting min row elements:


_ 1  2  3  4  5 _
|                 |
|  0  1  2  3  6  | 1
|  5  2  0  4  3  | 2
|  1  3  2  0  3  | 3
|  1  2  0  1  2  | 4
|  3  2  1  0  2  | 5
|_               _|


After subtracting the minimum column elements:


_ 1  2  3  4  5 _
|        |  |  |  |
|--0--0--2--3--5--| 1
|  5  1  0  4  1  | 2
|  1  2  2  0  1  | 3
|  1  1  0  1  0  | 4
|  3  1  1  0  0  | 5
|_       |  |  | _|


The minimum number of lines to cover all zeros is 4: a horizontal line through row 1 and vertical lines through columns 3, 4 and 5. The minimum uncovered element is 1. Subtract from each uncovered element and add to each twice covered element (cells (1,3), (1,4) and (1,5)):


_ 1  2  3  4  5 _
|                 |
|  0* 0  4  5  7  | 1
|  4  0* 0  4  1  | 2
|  0  2  2  0* 1  | 3
|  0  0  0* 1  0  | 4
|  2  0  1  0  0* | 5
|_               _|


The minimum cover is now 5, by drawing a line through each column. A minimum assignment is indicated by *. For example, we assign person 1 to job 1, person 2 to job 2, person 3 to job 4, person 4 to job 3, and person 5 to job 5. (There are alternative optimal assignments.)