liveBook · Manning

Column reduction

As explained in Algorithms Every Programmer Should Know

Column reduction subtracts a column’s minimum value from every entry in that column.

In a cost matrix, column reduction means finding each column’s minimum and subtracting it from every value in that column. It follows row reduction in the Hungarian algorithm, helping expose zero-cost assignment opportunities. section 3.1 section 3.4

Figure 3.3 The squares in step 1 are the minimum in each column of the cost matrix after row reduction. These minimum values are used, and column reduction is performed. The column Floors is only modified and subtracted by 1.

See the column minima after row reduction and how subtracting them changes the matrix. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains the subtraction procedure and shows its place after row reduction, without detailing an implementation.
Examples
Shows column minima of 0, 1, and 0 in a worker-to-task cost matrix after row reduction.
What it assumes
Assumes a cost matrix and uses row reduction before column reduction.
What you can do after
Apply column reduction by subtracting each column’s minimum from all values in that column.
How it connects
Connects column reduction to the Hungarian algorithm, row reduction, cost matrices, and the assignment problem.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.