The Hungarian Method (Balanced Minimisation)

The Hungarian method solves a balanced ($n \times n$) minimisation assignment problem exactly. It rests on one key idea: adding or subtracting a constant to every entry of a whole row (or a whole column) does not change which assignment is optimal — it only shifts the total cost by that constant. So we may reduce the matrix to one full of zeros in convenient places, and then read off an assignment that uses only zero-cost cells; that assignment is optimal for the reduced matrix, and hence for the original.

The algorithm, step by step.

Step 1 — Row reduction. In each row, find the smallest entry and subtract it from every entry of that row. Now every row has at least one zero.

Step 2 — Column reduction. In the resulting matrix, in each column, find the smallest entry and subtract it from every entry of that column. Now every row and every column has at least one zero.

Step 3 — Make the assignment (zero-covering test). Try to assign one zero in each row so that no two chosen zeros share a column:

• Scan rows (and columns) that contain exactly one unmarked zero. Box $\left[\;0\;\right]$ that zero (assign it) and cross out every other zero in its row and column.
• Repeat until every zero is either boxed or crossed out.

If you can box $n$ zeros — one in every row and every column — the assignment is complete and optimal. Stop.

Step 4 — Draw minimum covering lines (only if fewer than $n$ zeros could be boxed). Cover all the zeros of the matrix using the fewest possible horizontal and vertical lines. (A quick way: tick every row with no assignment; then tick every column having a zero in a ticked row; then tick every row having an assignment in a ticked column; repeat; finally draw lines through unticked rows and ticked columns.) The number of lines will be less than $n$. …