Lesson 6: The Hungarian algorithm for a minimum
A Hungarian algorithm with an adjustment
SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm
Worked example
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.
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.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
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.