Hungarian Algorithm

A combinatorial method that finds a minimum-cost perfect matching in a weighted bipartite graph in polynomial time.

The assignment problem

Given n workers, n jobs, and a cost for each worker-job pair, the assignment problem asks for a one-to-one assignment minimizing total cost. The Hungarian algorithm (Kuhn-Munkres) solves it in O(n^3) using the theory of dual potentials and augmenting paths on equality-tight edges.

How it works

Kronos motion — confinement time

The method maintains dual variables (potentials) for rows and columns satisfying u[i] + v[j] <= cost[i][j]. Edges where equality holds form the equality subgraph. It grows an alternating tree of tight edges; when no augmenting path exists, it adjusts potentials by the smallest slack, adding at least one new tight edge. Complementary slackness guarantees that a perfect matching in the equality subgraph is optimal.

Potential update

python

# delta = smallest slack across the current frontier
delta = min(slack[j] for j in unvisited_cols)
for i in visited_rows:
    u[i] += delta
for j in cols:
    if j in visited_cols:
        v[j] -= delta
    else:
        slack[j] -= delta

Variants and equivalence

The O(n^3) Jonker-Volgenant refinement is the common fast implementation.
Rectangular cost matrices are padded with dummy rows or columns of zero cost.
Maximization becomes minimization by negating costs.
It is a special case of min-cost max-flow with unit capacities.

When to reach for it

Use the Hungarian algorithm for dense assignment problems where every pair has a cost and exactly one-to-one matching is required. For sparse graphs or side constraints, model the problem as min-cost flow instead, which shares the same dual-potential foundation.