Allocation problems

The Hungarian algorithm

Assign $n$ workers to $n$ tasks at least total cost. The Hungarian algorithm reduces rows then columns so each has a zero; cover all zeros with the fewest lines; if fewer than $n$ lines, subtract the smallest uncovered value from uncovered cells and add it at intersections. With $n$ lines an optimal allocation of zeros exists.