305. Hungarian Algorithm

The classical algorithm for the assignment problem. Kuhn (1955), based on work by Hungarian mathematicians Egerváry & König.

305.1. Algorithm (intuition)

Given an 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 .

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

305.3. Worked example

After row reduction (subtract row mins ):

After column reduction (subtract column mins ):

Cover all zeros: rows 2, 4 and column 3 cover all zeros — 3 lines for an 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 .

305.4. Why

Each “augmenting path” step (finding more zeros to expose) costs via a labeling procedure. At most augmenting paths needed (each adds at least one matched pair). Total .

Modern variants:

305.5. See also