Understanding the Hungarian Matching Algorithm

What Does It Solve?

The Hungarian Matching Algorithm solves the assignment problem:

“How do we assign n tasks to n agents such that the total cost is minimized (or total profit is maximized)?”

Think of it like:

• Assigning jobs to workers
• Matching predicted boxes to GT boxes
• Matching students to schools optimally

Example Problem

We have 3 workers and 3 jobs. Each cell in the cost matrix shows how much it costs to assign a worker to a job.

Cost Matrix:
          Job1 Job2 Job3
Worker1    9     2     7
Worker2    6     4     3
Worker3    5     8     1

We want to assign each worker to one job so that the total cost is minimized.

Algorithm Intuition

The Hungarian algorithm operates in phases:

[1] Subtract Row Minimums     → Make sure each row has a zero
[2] Subtract Column Minimums  → Ensure each column has a zero
[3] Star Zeros                → Mark independent zeros (no overlap in row/column)
[4] Cover Columns with Stars  → Try to cover all assignments
[5] If not optimal:
    ↓ Find and prime new zeros
    ↓ Update covers and create alternating paths
    ↓ Adjust matrix (add/subtract smallest uncovered value)
Repeat until all rows assigned

Pseudocode Breakdown

Here’s the pseudocode logic:

Input: cost_matrix[n][n]

1. For each row, subtract the minimum value from each element in the row
2. For each column, subtract the minimum value from each element in the column

3. Star zeros:
   - For each zero, if its row and column are not covered, star it
   - Cover the row and column temporarily

4. Cover columns with stars
   - If all columns are covered, we're done
   - Else, go to step 5

5. While not all columns are covered:
   a. Find an uncovered zero, prime it
   b. If there is no starred zero in the same row:
       - Construct alternating path of stars and primes
       - Unstar stars, star primes along the path
       - Clear covers, go back to step 4
   c. Else:
       - Cover the row, uncover the column of the star
       - Repeat search

6. If no uncovered zeros:
   - Find the smallest uncovered value
   - Subtract it from all uncovered elements
   - Add it to elements covered twice
   - Go back to step 5

Step-by-Step Example

Let’s apply the Hungarian Algorithm to this matrix:

[9, 2, 7]
[6, 4, 3]
[5, 8, 1]

Subtract row mins:

Row mins = [2, 3, 1]
Result:
[7, 0, 5]
[3, 1, 0]
[4, 7, 0]

Subtract column mins:

Column mins = [3, 0, 0]
Result:
[4, 0, 5]
[0, 1, 0]
[1, 7, 0]

Star non-overlapping zeros:

[4, *0, 5]
[*0, 1, 0] ← overlapping
[1, 7, *0]

Final stars:
(0,1), (1,0), (2,2)

→ Covered columns = 3 → All matched!

References

1. Hungarian Algorithm (Wikipedia): https://en.wikipedia.org/wiki/Hungarian_algorithm
2. Hungarian Algorithm Illustrated: https://brc2.com/the-algorithm-workshop/