The Hungarian Method (also known as the Kuhn-Munkres algorithm) is a combinatorial optimization algorithm used to
solve the assignment problem. The assignment problem involves assigning 𝑛 workers to 𝑛 jobs such that the total cost (or
profit) is minimized (or maximized). The costs are typically represented in a square matrix where each element represents
the cost of assigning a particular worker to a particular job.
Example.
In this example, we will consider the following cost matrix where each cell represents the cost of assigning a worker to a
job:
Worker/Job J1 J2 J3 J4
W1 9 2 7 8
W2 6 4 3 7
W3 3 6 5 9
W4 7 8 6 4
Steps of the Hungarian Method:
1. Subtract the row minimum from each row:
For each row, subtract the smallest element in that row from all elements in that row.
• Row 1: The minimum is 2, so subtract 2 from each element of row 1:
9 − 2, 2 − 2, 7 − 2, 8 − 2 ⟹ 7, 0, 5, 6
• Row 2: The minimum is 3, so subtract 3 from each element of row 2:
6 − 3, 4 − 3, 3 − 3, 7 − 3 ⟹ 3, 1, 0, 4
• Row 3: The minimum is 3, so subtract 3 from each element of row 3:
3 − 3, 6 − 3, 5 − 3, 9 − 3 ⟹ 0, 3, 2, 6
• Row 4: The minimum is 4, so subtract 4 from each element of row 4:
7 − 4, 8 − 4, 6 − 4, 4 − 4 ⟹ 3, 4, 2, 0
Now the matrix looks like this:
Worker/Job J1 J2 J3 J4
W1 7 0 5 6
W2 3 1 0 4
W3 0 3 2 6
W4 3 4 2 0
2. Subtract the column minimum from each column:
Now, for each column, subtract the smallest element in that column from all elements in that column.
• Column 1: The minimum is 0, so no change to column 1.
• Column 2: The minimum is 0, so no change to column 2.
• Column 3: The minimum is 0, so no change to column 3.
• Column 4: The minimum is 0, so no change to column 4.
After this step, the matrix is still the same:
Worker/Job J1 J2 J3 J4
W1 7 0 5 6
W2 3 1 0 4
W3 0 3 2 6
W4 3 4 2 0
3. Cover all zeros with a minimum number of horizontal and vertical lines:
We now look to cover all the zeros in the matrix with the minimum number of horizontal and vertical lines.
We can cover all zeros with the following lines:
• Line 1: Cover the first row (W1), since it has a zero in column J2.
• Line 2: Cover the second column (J2), as it has a zero in W1 and W3.
• Line 3: Cover the fourth column (J4), since it has a zero in W4.
The resulting cover of zeros looks like this:
Worker/Job J1 J2 J3 J4
W1 7 0 5 6
W2 3 1 0 4
W3 0 3 2 6
W4 3 4 2 0
We have covered the zeros with 4 lines.
4. Check if the number of lines is equal to 𝒏 (the number of rows or columns):
The number of lines is 4, which is equal to 4 (the size of the matrix). Therefore, we are done with the iteration. we will
assign workers to jobs where the value is zero. This is the optimal assignment:
Note: If the number of lines used to cover the zeroes is not equal to the size of the matrix we need to proceed to the next
step.
Worker/Job J1 J2 J3 J4
W1 7 0 5 6
W2 3 1 0 4
W3 0 3 2 6
W4 3 4 2 0
• 𝑊1 → 𝐽2
• 𝑊2 → 𝐽3
• 𝑊3 → 𝐽1
• 𝑊4 → 𝐽4
The total minimum cost is the sum of the original costs at these positions:
Worker/Job J1 J2 J3 J4
W1 9 2 7 8
W2 6 4 3 7
W3 3 6 5 9
W4 7 8 6 4
• 𝑊1 → 𝐽2, Cost =2
• 𝑊2 → 𝐽3, Cost = 3
• 𝑊3 → 𝐽1, Cost = 3
• 𝑊4 → 𝐽4, Cost =4
Thus, the minimum total cost = 2 + 3 + 3 + 4 = 12.
Summary
Using the Hungarian Method, we were able to find the optimal assignment of workers to jobs with a total cost of 12.
