308. Hungarian Algorithm

The classical $𝑂\left({𝑛}^3\right)$ algorithm for the assignment problem. Kuhn (1955), based on work by Hungarian mathematicians Egerváry & König.

308.1. Algorithm (intuition)

Given an $𝑛\times 𝑛$ cost matrix $𝐶$:

1. Row reduction: subtract each row’s minimum from that row
2. Column reduction: subtract each column’s minimum from that column
3. Cover all zeros using the minimum number of horizontal / vertical lines
4. If lines = $𝑛$: an optimal assignment exists among the zeros — extract it
5. If lines < $𝑛$: adjust the matrix (subtract the minimum uncovered value from uncovered entries, add it to entries at line intersections) and go back to step 3

Repeat until step 4 succeeds. Termination in $𝑂\left({𝑛}^3\right)$.

308.2. Why it works

Each step preserves the relative cost structure: subtracting a constant from a row doesn’t change which assignment is optimal. The reductions create zeros — and an assignment using only zero-cost cells (when one exists) is necessarily optimal because all assignments have the same total constant subtracted.

The “cover” check finds when enough zeros exist to form a complete assignment. The adjustment step exposes more zeros without changing optimal-assignment structure.

308.3. Worked example

After row reduction (subtract row mins $2,3,1,4$):

After column reduction (subtract column mins $3,0,0,0$):

Cover all zeros: rows 2, 4 and column 3 cover all zeros — 3 lines for an $𝑛=4$ matrix → need to adjust.

(Continue iterations…)

Final assignment: agent 1 → task 2, agent 2 → task 1, agent 3 → task 3, agent 4 → task 4. Total cost $=2+6+1+4=13$.

308.4. Why $𝑂\left({𝑛}^3\right)$

Each “augmenting path” step (finding more zeros to expose) costs $𝑂\left({𝑛}^2\right)$ via a labeling procedure. At most $𝑛$ augmenting paths needed (each adds at least one matched pair). Total $𝑂\left({𝑛}^3\right)$.

Modern variants:

• Jonker–Volgenant — $𝑂\left({𝑛}^3\right)$ with smaller constants
• Auction algorithm (Bertsekas) — different paradigm, also $𝑂\left({𝑛}^3\right)$ but parallelizable
• Sparse Hungarian — $𝑂\left(𝑚\sqrt{𝑛}\right)$ for sparse graphs

308.5. See also

• Assignment Problem — the problem being solved
• Transportation Problem — generalization