The assignment problem
Suppose every worker has a different cost to do every job, given as a square table. You must assign each worker to exactly one job, and each job to exactly one worker, minimizing the total cost. Trying every assignment grows explosively, so we need structure.
Why subtracting helps
The Hungarian algorithm rests on a key fact: subtracting a constant from an entire row or an entire column does not change which complete assignment is cheapest. It only shifts every total by the same amount. So we can manipulate the table to create useful zeros without altering the answer.
The procedure in spirit
- Subtract the smallest value in each row from that row, then do the same for each column. Now every row and column holds at least one zero.
- Try to choose a set of zeros forming a complete assignment, one per row and column.
- If you cannot, cover all zeros with as few lines as possible, then adjust uncovered entries and repeat.
When a complete set of zeros exists, those positions give the minimum cost assignment.
Why it matters
It solves assignment in polynomial time rather than the brute force factorial blowup, and it is a clean special case of minimum cost matching.
Key idea
The Hungarian algorithm exploits that row and column subtractions preserve the optimal assignment, repeatedly creating zeros until a complete zero assignment appears.