liveBook · Manning

Row reduction

As explained in Algorithms Every Programmer Should Know

Row reduction is the operation of subtracting a row's minimum entry from every entry in that row of a matrix.

Row reduction prepares a cost matrix for the Hungarian algorithm: find the smallest entry in each row, then subtract it from every entry in that row. Each row’s minimum becomes zero, exposing possible low-cost assignments. section 3.1 section 3.4

Subtract each row’s minimum

In a worker-to-task cost matrix, Alice’s row minimum is 9, Bob’s is 9, and Carol’s is 8. Subtract each minimum from every entry in its row before proceeding to column reduction. section 3.1

Figure 3.2 The circled values in the cost matrix are the minimum values in respective rows. Row reduction is performed, and each value in the row is subtracted from the minimum value in that row.

The figure marks each row minimum and shows the matrix after subtracting those minima across the rows. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains how to subtract each row minimum and illustrates the result, then proceeds to column reduction and assignment checks.
Examples
Uses worker-task costs with row minima of 9, 9, and 8, plus a developer-module matrix measured in hours.
What you can do after
Apply row reduction by finding each row’s minimum and subtracting it from every entry in that row.
How it connects
Connects row reduction to the Hungarian algorithm, cost matrices, column reduction, 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.