The Assignment Problem

Four programmers, four tickets. Each person would take a different amount of time on each ticket — some are quick at front-end work, some at databases. You must give each person exactly one ticket and each ticket exactly one person, and you want the total time spent to be as small as possible. That one-to-one matching under cost is the assignment problem: pair n agents with n tasks at minimum total cost. It is everywhere — assigning crews to flights, jobs to machines, players to positions, kidneys to recipients.

The model

Let c_{ij} be the cost of giving agent i task j, and let the decision x_{ij}=1 mean "agent i does task j" and 0 otherwise. Then:

\min \sum_{i}\sum_{j} c_{ij}x_{ij} \quad\text{s.t.}\quad \sum_j x_{ij}=1,\;\; \sum_i x_{ij}=1,\;\; x_{ij}\in\{0,1\}.

The first constraint says each agent gets exactly one task; the second says each task gets exactly one agent. Notice the shape: this is precisely a transportation problem in which every supply and every demand equals 1. And because transportation problems are totally unimodular, we can drop the awkward x_{ij}\in\{0,1\} to a plain 0 \le x_{ij}\le 1 and the optimum still comes out as clean 0/1 assignments — for free.

It is a bipartite matching

Draw agents on the left and tasks on the right; an allowed pairing is an edge. A valid assignment picks edges so that every left node and every right node is touched exactly once — a perfect matching in a bipartite graph. The assignment problem is that matching's minimum-cost version.

The highlighted edges form one complete matching: every programmer is joined to exactly one ticket, and every ticket to exactly one programmer. Of all such matchings, we want the cheapest.

A cost matrix to solve

Times (in hours) for four programmers on four tickets:

	Ticket 1	Ticket 2	Ticket 3	Ticket 4
Ada	9	2	7	8
Bhavna	6	4	3	7
Chen	5	8	1	8
Dmitri	7	6	9	4

Twenty-four full assignments are possible (4! = 24). Enumerating them is fine here but hopeless at scale — 20! \approx 2.4\times10^{18}. We need a real algorithm.

The Hungarian method

The classic exact algorithm, published by Harold Kuhn in 1955 and named for the earlier work of the Hungarian mathematicians König and Egerváry, rests on one lovely fact: subtracting a constant from every entry of a row (or column) does not change which assignment is optimal — it only shifts the total by that constant. So we massage the matrix until a zero-cost assignment appears.

Row reduction — subtract each row's smallest entry from that whole row, creating a zero in every row.
Column reduction — do the same down each column.
Cover the zeros — draw the fewest horizontal/vertical lines that cover all zeros. If that number equals n, an all-zero (hence optimal) assignment exists — read it off.
Create more zeros — if fewer than n lines suffice, subtract the smallest uncovered value from all uncovered entries, add it where lines cross, and cover again. Repeat.

It finishes in O(n^3) time — polynomial, dramatically faster than the n! brute force, and it always returns the guaranteed optimum.

The Hungarian method wants a square matrix, but life is rarely square: perhaps five jobs and only three machines. The trick is the same as balancing a transportation problem — pad the matrix to a square with dummy rows or columns whose costs are all zero (a "task" assigned to a dummy agent is simply a task left undone, at no modelled cost). Assign, then discard the dummy pairings. Maximisation problems (assign salespeople to territories to maximise revenue) are handled by first negating the matrix, or subtracting every entry from the largest, turning "most profit" into "least regret".

It is tempting to solve an assignment by repeatedly taking the smallest remaining cost and locking in that pair. This greedy approach is often wrong: grabbing Chen→Ticket 3 (cost 1) looks irresistible, but it may force a wildly expensive pairing later that a slightly worse first choice would have avoided. Assignment costs are entangled — one choice removes a whole row and a whole column from play. Only a method that weighs the whole matrix at once, like the Hungarian method, guarantees the true minimum. Local bargains can cost you globally.