Lesson 6: The Hungarian algorithm for a minimum

A 4×44 \times 4 Hungarian algorithm with an adjustment

SkillsMinimum assignment (Hungarian)Steps of the Hungarian algorithm

Worked example

  • Complex familiar

A building company has four electricians, Asha (AA), Ben (BB), Chloe (CC) and Dan (DD), 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.

1234A111266B18102015C91996D126711\begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline A & 11 & 12 & 6 & 6 \\ B & 18 & 10 & 20 & 15 \\ C & 9 & 19 & 9 & 6 \\ D & 12 & 6 & 7 & 11 \end{array}
1 of 7 steps
  1. Step 1: Row reduction

    Subtract 6, 10, 6 and 6 from rows AA, BB, CC and DD:

    1234A5600B80105C31330D6015\begin{array}{c|cccc} & 1 & 2 & 3 & 4 \\ \hline A & 5 & 6 & 0 & 0 \\ B & 8 & 0 & 10 & 5 \\ C & 3 & 13 & 3 & 0 \\ D & 6 & 0 & 1 & 5 \end{array}

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Row reduce, then column reduce.

  2. Cover the zeros with the fewest lines.

  3. If fewer than nn lines: subtract the smallest uncovered entry from uncovered entries, add it where lines cross, and cover again.

  4. 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.

Save your progress with a free account