Lesson 6: The Hungarian algorithm for a minimum
A Hungarian algorithm with no adjustment
SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm
Worked example
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.
Answer
– suburb 3, – suburb 1, – suburb 2, with a minimum total time of 20 minutes.
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; 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.