Assignment Problem & Hungarian Method

The assignment problem asks: assign n workers to n jobs, one each, so that total cost (or time) is minimum. Each worker-job pair has a known cost, and every job must be done exactly once.

It matters because matching problems are everywhere: scheduling staff to shifts, assigning machines to tasks, allocating salespeople to territories. A wrong assignment wastes money every single day, so finding the proven-best match is valuable.

Key Concepts

• Cost matrix: the n×n table of costs cᵢⱼ for worker i doing job j.
• One-to-one constraint: each worker gets exactly one job and each job exactly one worker.
• Balanced problem: equal numbers of workers and jobs; otherwise add dummy rows/columns with zero cost.
• Opportunity cost: the penalty of not choosing the cheapest option in a row or column.
• Hungarian method: the classic algorithm that finds the optimal assignment.

How It Works

1. Write the n×n cost matrix.
2. Subtract the smallest value in each row from every element of that row.
3. Subtract the smallest value in each column from every element of that column.
4. Cover all zeros with the minimum number of lines (rows + columns).
5. If the number of lines equals n, an optimal assignment of zeros exists — pick them. Otherwise, find the smallest uncovered value, subtract it from uncovered elements, add it to doubly-covered ones, and repeat step 4.

Worked Example

Cost matrix (workers A, B, C; jobs 1, 2, 3): A: [8, 4, 7], B: [5, 2, 3], C: [9, 4, 8].

1. Row reduction: A: [4, 0, 3], B: [3, 0, 1], C: [5, 0, 4].
2. Column reduction: col 1 min 3, col 2 min 0, col 3 min 1 → A: [1, 0, 2], B: [0, 0, 0], C: [2, 0, 3].
3. Cover zeros: row B (three zeros) + column 2 → 2 lines < 3. Smallest uncovered = 1 (A1, C1): subtract from uncovered, add to doubly covered (B2): A: [0, 0, 1], B: [0, 1, 0], C: [1, 0, 2].
4. Cover zeros: 3 lines = 3 ✓. Assign: A→2 (0), B→3 (0), C→1 (0) — valid, one per row and column.
5. Original cost: A2 = 4, B3 = 3, C1 = 9 → total 16.

Check alternatives: A→2 (4) + B→1 (5) + C→3 (8) = 17; A→3 (7) + B→2 (2) + C→1 (9) = 18. So 16 is indeed minimal.

Common Misconceptions

• "Assign each worker their cheapest job." Two workers may share a cheapest job; the global optimum balances conflicts.
• "Subtracting numbers changes the answer." Row and column reductions shift every complete assignment's total by the same constant, so the optimum is unchanged.
• "It only works for minimisation." Maximisation problems convert by subtracting all entries from the largest cost.

Real-World Applications

• Airlines assign pilots and crew to flight rosters.
• Hospitals roster nurses to shifts fairly and cheaply.
• Delivery companies assign drivers to routes each morning.

The assignment problem turns matching decisions into a solvable cost matrix. The Hungarian method finds the provably cheapest one-to-one matching in polynomial time — far better than trying all n! possibilities.