Lesson 6 of 7 · 20 min
The Hungarian algorithm for a minimum
Use row reduction, column reduction, covering lines and the adjustment step to find the allocation with the smallest total cost or time for a 3 × 3 to 5 × 5 problem.
What you will be able to do
- Explain why subtracting a number from a whole row or column does not change the best allocation.
- Reduce the rows and columns of a cost matrix.
- Cover all the zeros with the fewest lines, and decide whether an assignment can be made.
- Carry out the adjustment step, then read the optimal assignment from the zeros and total it from the original table.
Every complete allocation uses exactly one entry from each row and exactly one from each column. That simple fact is the key to the Hungarian algorithm, named after the Hungarian mathematicians whose work it is built on.
Suppose a technician charges $5 more than you thought for every job. Every allocation now costs $5 more, so the cheapest allocation is still the cheapest. In the same way, you can subtract a number from every entry of a row — or of a column — without changing which allocation is best. Do it cleverly and you create zeros, and an allocation that uses only zeros must be optimal: nothing can cost less than 0.
The Hungarian algorithm (minimum)
Row reduction
Subtract the smallest entry in each row from every entry in that row.
Column reduction
Subtract the smallest entry in each column from every entry in that column. (A column that already has a 0 is unchanged.)
Cover the zeros
Cover all the zeros with the fewest horizontal and vertical lines. For an matrix, if lines are needed, go to step 5.
Adjust
If fewer than lines are enough, find the smallest uncovered entry. Subtract it from every uncovered entry, add it to every entry covered by two lines, and leave the rest. Go back to step 3.
Assign
Choose one zero in each row and each column. Start with any row or column that has only one zero. Total the assignment from the original table.
Worked example
A Hungarian algorithm with no adjustment
Three couriers, , and , can each cover one of three suburbs. The table gives the delivery time in minutes. Use the Hungarian algorithm to find the allocation with the least total time.
Step 1: Row reduction
Subtract each row's smallest entry (4, 5 and 9):
Step 2: Column reduction
Columns 1 and 3 already have a zero. Column 2's smallest entry is 2, so subtract 2 from column 2:
Step 3: Cover the zeros
The zeros at , and are in different rows and columns, so no two lines can cover all of them: 3 lines are needed (for example the three columns). , so an assignment can be made.
Step 4: Assign
has one zero, in column 3, so – 3. has one zero, in column 1, so – 1. That leaves – 2, which is a zero.
Step 5: Total from the original table
minutes.
Try it yourself first, then check the working one step at a time.
Answer
– suburb 3, – suburb 1, – suburb 2, with a minimum total time of 20 minutes.
Method
Row reduce, then column reduce.
Cover the zeros with the fewest lines; lines means assign.
Assign one zero per row and column, and total from the original table.
Watch out for
Skipping column reduction: after row reduction, column 2 has no zero, and you can't complete an assignment from the zeros.
Row reduce this cost matrix.
Often the zeros don't line up into a complete assignment straight away. The covering lines test tells you when they do: if you can cover every zero with fewer than lines, there aren't enough independent zeros yet, and the adjustment step creates more.
Times in hours for four electricians to do four jobs. Step through: watch where the covering lines go, and how the adjustment creates a new zero.
Worked example
A Hungarian algorithm with an adjustment
A building company has four electricians, Asha (), Ben (), Chloe () and Dan (), and four jobs. The table shows the time in hours each would take on each job. Use the Hungarian algorithm to allocate one job to each electrician so that the total time is as small as possible.
Step 1: Row reduction
Subtract 6, 10, 6 and 6 from rows , , and :
Step 2: Column reduction
Column 1 has no zero; its smallest entry is 3. The other columns already have zeros.
Step 3: Cover the zeros
Lines through row , row and column 2 cover every zero. Only 3 lines are needed, and , so an assignment can't be made yet.
Row holds two zeros and row two more; column 2 catches and . With 3 lines there are not 4 zeros in different rows and columns.
Step 4: Adjust
The uncovered entries are 5, 10, 5 (row ) and 3, 1, 5 (row ). The smallest is 1. Subtract 1 from each uncovered entry and add 1 where lines cross ( and ):
Step 5: Cover again
The new zero at means 4 lines are now needed (for example all four columns). , so assign.
Step 6: Assign, forced choices first
has only one zero: – 2. Then 's zeros are in columns 2 and 3, and 2 is taken, so – 3. 's zeros are in columns 3 and 4, so – 4. That leaves – 1.
Step 7: Total from the original table
hours.
Try it yourself first, then check the working one step at a time.
Answer
Asha – Job 4, Ben – Job 2, Chloe – Job 1, Dan – Job 3, with a minimum total of 32 hours. It is the only optimal allocation.
Method
Row reduce, then column reduce.
Cover the zeros with the fewest lines.
If fewer than lines: subtract the smallest uncovered entry from uncovered entries, add it where lines cross, and cover again.
Assign from the zeros, forced choices first; total from the original table.
Watch out for
Adding the 1 to every covered entry instead of only where two lines cross.
Stopping at the first set of lines and trying to assign with only 3 independent zeros — someone ends up with no zero.
Three lines (rows and , column 2) cover every zero. , so adjust. The uncovered entries are 5, 10, 5, 3, 1 and 5; the smallest is 1.
Key idea
The adjustment step
With the smallest uncovered entry:
- uncovered entries: subtract ;
- entries covered by two lines (where lines cross): add ;
- entries covered by one line: unchanged.
This creates at least one new zero where was, while keeping every entry 0 or more.
What is the fewest number of lines needed to cover all the zeros in this reduced matrix?
Common mistake
Totalling the reduced matrix
The final matrix tells you who does what — its chosen entries are all 0. Go back to the original table for the total: hours in the example, not 0.
Exam tip
Show every matrix: after row reduction, after column reduction, with the lines drawn (or listed: "lines through rows , and column 2"), and after each adjustment. State "3 lines < 4, so adjust" or "4 lines = 4, so assign". Finish with the allocation and its total, with units.
Summary
Subtracting a number from a whole row or column changes every allocation's total by the same amount, so the best allocation is unchanged.
Reduce the rows, then the columns, so that every row and column has a zero.
Cover all the zeros with the fewest lines. lines for an matrix means an optimal assignment exists.
Otherwise adjust: subtract the smallest uncovered entry from uncovered entries and add it where two lines cross.
Assign using one zero per row and column (forced choices first), and total from the original table.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.