The assignment problem
Given a square cost table of workers against jobs, the assignment problem asks for a one to one pairing of each worker to a job that minimizes the total cost. Trying every pairing is far too slow as the table grows.
Potentials and tight edges
The Hungarian algorithm keeps a number, called a potential, on every row and column. An edge is tight when its cost equals the sum of its row and column potentials. The algorithm only ever matches along tight edges, and it adjusts potentials to create new tight edges where they are needed.
- Build a partial matching using current tight edges.
- When no augmenting path exists, shift potentials to expose a new tight edge.
- Repeat until every worker is matched.
Why it is optimal
The potentials act as a certificate. Total cost is always at least the sum of all potentials, and when a full matching of tight edges is reached, the matching cost equals that sum. Meeting the bound proves the assignment is the cheapest possible.
Key idea
Maintain row and column potentials, match only tight edges, and shift potentials until a full minimum cost assignment certifies itself.