Why does the Hungarian Method solve the assignment problem efficiently?

Answer First

The Hungarian Method is efficient because it transforms the assignment problem into a sequence of matrix reductions and matchings that guarantee an optimal solution without checking all permutations.

It works in O(n³) time — dramatically faster than the exponential alternatives.

• Reduces the cost matrix
• Creates zero‑cost opportunities
• Finds a perfect matching using only zeros
• Adjusts the matrix when a perfect matching is not yet possible

Step-by-Step: Why the Hungarian Method Works

Step 1: Subtract Row Minimums

Each row is reduced so that every worker has at least one zero‑cost option.

Step 2: Subtract Column Minimums

Each column is reduced so that every task has at least one zero‑cost candidate.

Step 3: Cover All Zeros with Minimum Lines

If the number of lines equals n, a perfect assignment exists using only zeros.

Step 4: Adjust the Matrix if Needed

If not enough zeros exist, the algorithm:

• finds the smallest uncovered value
• subtracts it from uncovered cells
• adds it to cells covered twice

This creates new zeros while preserving optimality.

Step 5: Find a Perfect Matching

Once enough zeros exist, the algorithm selects one zero per row and column — the optimal assignment.

Numerical Example

Cost matrix:

\[ \begin{bmatrix} 9 & 2 & 7 \\ 6 & 4 & 3 \\ 5 & 8 & 1 \end{bmatrix} \]

Step 1: Row Reductions

Subtract row minimums → new matrix:

\[ \begin{bmatrix} 7 & 0 & 5 \\ 3 & 1 & 0 \\ 4 & 7 & 0 \end{bmatrix} \]

Step 2: Column Reductions

Subtract column minimums → new matrix:

\[ \begin{bmatrix} 7 & 0 & 5 \\ 3 & 1 & 0 \\ 4 & 7 & 0 \end{bmatrix} \]

(Column reductions already satisfied.)

Step 3: Find Zero Assignments

A perfect matching exists:

• Worker 1 → Task 2
• Worker 2 → Task 3
• Worker 3 → Task 1

Total cost = 2 + 3 + 5 = 10 (optimal)