Assignment Problem / Hungarian Algorithm

Min-cost perfect matching by row and column reduction.

The idea

The assignment problem asks for the cheapest way to give $n$ agents $n$ tasks, one each, when putting agent $i$ on task $j$ costs $c_{ij}$. There are $n!$ assignments, so trying them all is out of reach even for modest $n$.

The Hungarian algorithm solves the problem exactly, in time polynomial in $n$: it always returns an assignment of minimum total cost, never merely a good one.

It rests on one observation about the cost matrix $C = (c_{ij})$. Every assignment uses exactly one cell from each row and one from each column, so subtracting a constant from an entire row lowers every assignment's total by that same constant and leaves the ranking of assignments unchanged. The same holds for a column.

The algorithm uses this observation to reshape the matrix until a zero-cost assignment appears.

Algorithm.

Algorithm: Hungarian Algorithm Input: an n × n cost matrix C Output: an assignment of minimum total cost 1. subtract from each row its smallest entry, then from each column its smallest entry // costs stay ≥ 0; every row and column now holds a zero 2. look for a perfect matching of zero cells — one zero in each row and each column if one exists, return it // reduced total 0: nothing can beat it, so it is optimal in C too 3. cover all the zeros with as few horizontal and vertical lines as possible // fewer than n suffice, since step 2 failed 4. δ = the smallest uncovered entry; subtract δ from every uncovered entry, add δ to every twice-covered entry // more row and column subtractions; a new zero appears outside the lines 5. go to step 2

Ways to work on it

• Walkthrough. Row- and column-reduce a cost matrix, then read off the optimal assignment.
• Practice. Row-reduce a row of a cost matrix.
• Hardest. Use dual potentials to certify an assignment is optimal.

Not sure where to start? Take the ten-question placement test.