The Hungarian Method

The Hungarian Method

The Hungarian Method finds the optimal one-to-one assignment in a square cost matrix without checking every possible permutation (which grows as $n!$ and quickly becomes impractical).

Steps of the algorithm

1. Row reduction: In every row, subtract that row's smallest entry from every entry in the row.
2. Column reduction: In every column of the row-reduced matrix, subtract that column's smallest entry from every entry in the column.
3. Cover all zeros in the resulting matrix using the minimum possible number of horizontal and vertical lines.
4. Test optimality: If the number of lines used equals $n$ (the size of the matrix), an optimal assignment exists among the zeros — go to Step 6. If fewer than $n$ lines are needed, go to Step 5.
5. Adjust the matrix: Find the smallest uncovered entry. Subtract it from every uncovered entry, and add it to every entry lying at the intersection of two covering lines; leave entries covered by only one line unchanged. Return to Step 3.
6. Make the assignment: Select a set of independent zeros — one per row, one per column — from the final matrix. Compute the total cost by summing the corresponding entries in the original (pre-reduction) cost matrix.

Worked example

A company must assign three workers $W_1,W_2,W_3$ to three jobs $J_1,J_2,J_3$ at minimum total cost (₹ per job):

Step 1 — Row reduction (row minimums: $W_1\to8$, $W_2\to7$, $W_3\to9$):

Step 2 — Column reduction (column minimums: $J_1\to2$, $J_2\to0$, $J_3\to0$):

Step 3 — Cover the zeros: row $W_2$ covers its two zeros ($W_2J_1,W_2J_2$); column $J_3$ covers its two zeros ($W_1J_3,W_3J_3$) — all zeros covered using 2 lines.

Step 4 — Test: $2<n=3$ → not yet optimal.

Step 5 — Adjust: the smallest uncovered entry is $W_1J_1=1$. Subtract 1 from every uncovered cell ($W_1J_1,W_1J_2,W_3J_1,W_3J_2$) and add 1 to the intersection cell ($W_2J_3$, covered by both lines):

Step 3 (repeat): column $J_1$ (covers $W_1J_1,W_2J_1$), column $J_3$ (covers $W_1J_3,W_3J_3$), row $W_2$ (covers $W_2J_1,W_2J_2$) — all five zeros covered using 3 lines.

Step 4 (repeat): $3=n=3$ → optimal. …