Hungarian Method

Solves a balanced assignment problem in polynomial time, avoiding the degeneracy the transportation methods would hit.

Steps

• Row reduction: subtract the minimum entry of each row from every entry in that row.
• Column reduction: subtract the minimum entry of each column from every entry in that column.
• Cover all 0s in the resulting matrix using the minimum number of horizontal and vertical lines.
• If the number of lines equals $n$, an optimal assignment exists among the 0s. Stop.
• Otherwise, find the smallest uncovered entry. Subtract it from every uncovered entry, and add it to every entry covered twice (at a line intersection). Repeat the covering step.

Reading the Assignment

Once $n$ lines are needed, select $n$ independent 0s (1 per row and column) by assigning rows/columns with a unique 0 first, then resolving remaining choices, until every agent is assigned a task.