# Hungarian method

### From Glossary

An algorithm to solve the standard assignment problem (presented by H. Kuhn in 1955). Let C be the cost matrix.

- Step 0 (initialize). Subtract the least element of each row from that row of . Then, do likewise for each column. The resulting matrix, has a zero in every row and column. (Further, a least cost assignment for is also a least cost assignment for .) Re-define .
- Step 1 (cover zeros). Draw the minimum number of lines through the rows and columns to cover all zeros in . If that minimum is , you can assign to such that ; then you can remove row and column , repeating the process to obtain an optimal assignment. Otherwise, if that minimum is greater than , continue.
- Step 2 (revise ). 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.)