Column Reduction - Assignment & the Hungarian Method

After row reduction, the Hungarian method subtracts each column's minimum. This keeps the same optimum because every complete assignment uses exactly one entry from each column. The goal is to build enough zeros for a perfect assignment while preserving the original argmin exactly.

highlighted = computed this step

Column minima

The column minima are 1, 0, and 4. Why: subtracting them gives every column a zero too. The same preservation logic applies as in row reduction: each complete assignment uses exactly one entry from each column, so all assignments shift equally.

\text{column mins }1,0,4

Zeros in rows and columns

Highlighted zero cells are the candidates for a no-extra-cost assignment in the reduced matrix. The interpretation is relative cost: after subtracting row and column constants, a zero marks a worker-job pair that can be chosen without adding extra reduced cost. The method is trying to create enough such opportunities that one can be chosen in every row and every column at the same time. That is why zeros matter as a pattern, not just as isolated entries.

\text{look for one zero in each row and column}

Diagram note

The displayed entries are the recomputed column-reduced matrix. The optimal assignment is unchanged by the row and column shifts; only the bookkeeping has been reshaped so a zero-cost complete assignment can become visible. This preservation of the argmin is the core reason the reduction is valid. Pixel positions are rounded for layout; every number shown is exact.

\text{column reduction preserves the optimum}