Hungarian Method for Assignment Problems

The Hungarian method is an algorithm that solves assignment problems optimally: it matches n workers to n jobs at minimum total cost. Developed from the work of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, it was formalised by Harold Kuhn in 1955.

It matters because it guarantees the best possible assignment without checking every permutation. For 10 workers there are over 3.6 million permutations — the Hungarian method finds the optimum with a short series of matrix operations instead.

Key Concepts

• Cost matrix: the n×n table of assignment costs.
• Row/column reduction: subtracting row and column minima; creates zeros without changing the optimal assignment.
• Independent zeros: zeros no two of which share a row or column — a full set of n gives an optimal assignment.
• Minimum line cover: fewest lines covering all zeros; Kőnig's theorem says this equals the maximum number of independent zeros.
• Matrix adjustment: when lines < n, subtract the smallest uncovered value from uncovered cells and add it to twice-covered cells.

How It Works

1. Reduce rows: subtract each row's minimum from the row.
2. Reduce columns: subtract each column's minimum from the column.
3. Draw the minimum number of lines covering all zeros.
4. If lines = n, choose n independent zeros — that is the optimal assignment.
5. Otherwise, let k be the smallest uncovered value: subtract k from all uncovered elements and add k to elements covered twice. Go back to step 3.

The method terminates in a finite number of steps and always returns an optimal assignment for minimisation problems.

Worked Example

Matrix: P: [6, 5, 4], Q: [3, 4, 6], R: [7, 6, 5].

1. Row reduction: P: [2, 1, 0], Q: [0, 1, 3], R: [2, 1, 0].
2. Column reduction: col minima 0, 1, 0 → P: [2, 0, 0], Q: [0, 0, 3], R: [2, 0, 0].
3. Cover zeros: column 2 (P, Q, R zeros) + row Q → 2 lines < 3. Smallest uncovered: P1 = 2, P3 = 2, R1 = 2, R3 = 2 → k = 2.
4. Subtract 2 from uncovered, add 2 to doubly covered (Q2): P: [0, 0, 0], Q: [0, 2, 3], R: [0, 0, 0].
5. Now 3 lines cover all zeros. Independent zeros: P→3, Q→1, R→2. Original costs: P3 = 4, Q1 = 3, R2 = 6 → total 13.

Check: P→3 (4) + Q→2 (4) + R→1 (7) = 15; P→1 (6) + Q→2 (4) + R→3 (5) = 15. So 13 is the minimum.

Common Misconceptions

• "Zeros in the matrix mean zero cost." Zeros are created by reduction; they mark candidate cells, not free assignments.
• "One pass always suffices." The adjustment step may need repeating before n independent zeros appear.
• "It needs square matrices." Unbalanced problems add dummy rows or columns with zero cost first.

Real-World Applications

• Manufacturing plants assign operators to machines each shift.
• Exam boards assign examiners to papers for evaluation.
• Ride-hailing apps match drivers to riders as large assignment problems.

The Hungarian method's row and column reductions expose the structure hidden in the cost matrix, and the line-covering test tells exactly when the optimum is reached. It converts an impossible-seeming combinatorial search into a short, mechanical procedure.