Hungarian method

From Glossary

Jump to: navigation, search

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.)



Views
Personal tools