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)

  1. Row reduction

    Subtract the smallest entry in each row from every entry in that row.

  2. Column reduction

    Subtract the smallest entry in each column from every entry in that column. (A column that already has a 0 is unchanged.)

  3. Cover the zeros

    Cover all the zeros with the fewest horizontal and vertical lines. For an n×nn \times n matrix, if nn lines are needed, go to step 5.

  4. Adjust

    If fewer than nn 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.

  5. 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 3×33 \times 3 Hungarian algorithm with no adjustment

  • Simple familiar

Three couriers, AA, BB and CC, 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.

123A13104B5107C91112\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline A & 13 & 10 & 4 \\ B & 5 & 10 & 7 \\ C & 9 & 11 & 12 \end{array}
5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Row reduce, then column reduce.

  2. Cover the zeros with the fewest lines; nn lines means assign.

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

[94768510129]\begin{bmatrix} 9 & 4 & 7 \\ 6 & 8 & 5 \\ 10 & 12 & 9 \end{bmatrix}

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 nn lines, there aren't enough independent zeros yet, and the adjustment step creates more.

Interactive

Step through the Hungarian algorithm

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 4×44 \times 4 Hungarian algorithm with an adjustment

  • 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}
7 steps

Try it yourself first, then check the working one step at a time.

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.

Three lines (rows AA and CC, column 2) cover every zero. 3<43 < 4, so adjust. The uncovered entries are 5, 10, 5, 3, 1 and 5; the smallest is 1.

Key idea

The adjustment step

With mm the smallest uncovered entry:

  • uncovered entries: subtract mm;
  • entries covered by two lines (where lines cross): add mm;
  • entries covered by one line: unchanged.

This creates at least one new zero where mm 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?

[030205041]\begin{bmatrix} 0 & 3 & 0 \\ 2 & 0 & 5 \\ 0 & 4 & 1 \end{bmatrix}

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: 6+10+9+7=326 + 10 + 9 + 7 = 32 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 AA, CC 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. nn lines for an n×nn \times n 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.

Lesson 6 of 70% read

Save your progress with a free account