Match workers to jobs (or machines to tasks) so the total cost or time is as low as possible. It's a fixed, step-by-step recipe on a cost table, no guessing.
What even is this? An assignment problem: each worker does exactly one job, each job goes to exactly one worker, and you want the cheapest total. The Hungarian algorithm finds it by reducing a cost table until you can read the answer off the zeros.
If you only do one thingThe recipe: row reduce → column reduce → cover the zeros with the fewest lines → assign (one zero per row and column). If the fewest lines is less than n, adjust and try again.
The 10-minute version
row reduce → column reduce → cover zeros → assign
Subtract each row's smallest, then each column's smallest. Cover all zeros with the fewest lines, when that count equals the size, pick one zero in each row and column. Then do Practice Q1.
You have n workers and n jobs, with a cost (or time) for each worker doing each job, set out in a square cost table. Each worker takes exactly one job, and each job is done by exactly one worker. The goal: choose the matching with the smallest total cost. Checking every combination gets huge fast, the Hungarian algorithm is the tidy shortcut.
2 · The steps
1
Row reduction: in each row, subtract the smallest number from every number in that row.
2
Column reduction: in each column, subtract the smallest number from every number in that column.
3
Cover all zeros using the fewest possible straight lines (rows and columns).
4
If the number of lines equals n, you can make the assignment, pick one zero in each row and each column. If it's less than n, do the adjustment below and return to step 3.
5
Assignment: the chosen zeros tell you who does which job. Read the total cost off the original table.
If lines < n (adjustment): find the smallest uncovered number. Subtract it from every uncovered number, and add it to any number covered by two lines. Leave the rest. Then cover the zeros again.
3 · Worked example
🛠️ Three workers, three jobs
Costs (in $) for each worker on each job. Assign so the total cost is minimised.
Original cost table
J1
J2
J3
W1
9
11
14
W2
6
15
13
W3
12
13
6
After row reduce (−9, −6, −6)
J1
J2
J3
W1
0
2
5
W2
0
9
7
W3
6
7
0
After column reduce (−0, −2, −0)
J1
J2
J3
W1
0
0
5
W2
0
7
7
W3
6
5
0
Cover zeros & assign (3 lines = n, so assign)
J1
J2
J3
W1
0
0
5
W2
0
7
7
W3
6
5
0
The zeros can be covered with 3 lines (= n), so an assignment exists. Pick one zero per row and column: W1 → J2, W2 → J1, W3 → J3.
Read costs off the original table: W1→J2 = $11, W2→J1 = $6, W3→J3 = $6. Minimum total cost = $23.
4 · Practice questions
1. What are the first two steps of the Hungarian algorithm, in order?Tap to reveal
Row reduction (subtract each row's smallest), then column reduction (subtract each column's smallest).
2. You cover all the zeros in a 4×4 table and it takes only 3 lines. Can you assign yet?Tap to reveal
No. The number of lines (3) is less than n (4). You must do the adjustment, smallest uncovered subtracted from uncovered, added to double-covered, then cover again.
3. After the worked example you chose W1→J2, W2→J1, W3→J3. Why read the cost off the original table, not the reduced one?Tap to reveal
The reducing steps were just to find the best matching, they changed the numbers. The real dollar cost is the original $11 + $6 + $6 = $23.