Hungarian Method for Minimization in Assignment Problems

Understand Hungarian Method for Minimization

Key rules to remember

Row reduction

New cost = cost − smallest value in that row

Do this for every row. Each row now has at least one zero.

Column reduction

New cost = cost − smallest value in that column

Do this on the row-reduced matrix. Skip a column that already has a zero, because its minimum is 0.

Optimality test

Minimum number of lines covering all zeros = n ⇒ optimal assignment exists

If the lines are fewer than n, the solution is not yet optimal. Revise the matrix.

Matrix revision

k = smallest uncovered element; uncovered cells: subtract k; cells at line intersections: add k; cells covered once: unchanged

Repeat the line-covering test after each revision.

Total minimum cost

Total cost = Σ original cost of the assigned cells

Read the costs from the original matrix. Never add up the reduced values.

How to solve Hungarian Method for Minimization questions

1. 1Check that the number of rows equals the number of columns. If not, add a dummy row or column of zeros. If the objective is maximization, convert it first.
2. 2Row reduction: subtract the smallest element of each row from every element of that row.
3. 3Column reduction: in the new matrix, subtract the smallest element of each column from every element of that column.
4. 4Cover all zeros with the minimum number of horizontal and vertical lines. A tick method helps: tick rows with no assignment, tick columns with zeros in ticked rows, tick rows with assignments in ticked columns, and repeat. Then draw lines through unticked rows and ticked columns.
5. 5If the number of lines equals n, go to step 7. If fewer than n, find the smallest uncovered element k.
6. 6Subtract k from every uncovered element and add k to every element at a line intersection. Leave the other covered elements as they are. Go back to step 4.
7. 7Make the assignment. Start with a row or column that has a single zero, allot it, and strike out the rest of that row and column. Repeat. If there is a tie, choose any zero and continue.
8. 8Write the pairings and add their costs from the original matrix to get the minimum total cost.

Quickest way: Single-zero first, then check by reductions

Common mistakes in Hungarian Method for Minimization

• Adding up the reduced matrix values to get the total cost.

  The assigned cells show zeros or small numbers and students add what they see.

  Fix: Go back to the original matrix. Write each pairing with its original cost and add those costs.

• Doing column reduction before row reduction, or skipping it altogether.

  Students think one round of zeros is enough.

  Fix: Do rows first, then columns. Column reduction can create zeros in a column that had none, so it often changes the answer.

• Drawing more lines than needed, or lines that miss a zero.

  Students cover zeros by eye and do not check whether the count is minimum.

  Fix: Use the tick method. Count the lines. Compare with n before deciding whether to revise.

• Revising the matrix wrongly: subtracting k from covered cells or forgetting to add k at intersections.

  The rule has three cases and students mix them up.

  Fix: Uncovered: subtract k. Covered twice (intersection): add k. Covered once: leave unchanged. Check that the total of the matrix is consistent.

• Allotting a zero in a row or column that still has other zeros, and then getting stuck.

  Students pick the first zero they see.

  Fix: Always assign rows or columns that have only one unassigned zero first. Pick freely only when every remaining row and column has two or more zeros.

• Applying the method to a non-square matrix.

  Students start reducing without counting rows and columns.

  Fix: Check the matrix size first. Add a dummy row or column with zero cost to make it square.

Worked examples