liveBook · Manning

Uncovered number

As explained in Algorithms Every Programmer Should Know

An uncovered number is a matrix entry not crossed by any of the lines covering the current zero entries.

An uncovered number is a matrix entry that no line crosses when lines are drawn to cover the current zeros. In the Hungarian algorithm, the smallest uncovered number helps expose new zeros when the lines covering all zeros are fewer than the matrix size. section 3.1

To adjust the matrix:

  • Find the smallest uncovered number. section 3.1
  • Subtract it from every uncovered entry and add it to entries where two lines intersect. section 3.1
Figure 3.9 The dotted box in step 3 is the value of the smallest number uncovered. This number is subtracted from all the uncovered values. The same value is added to the intersection of the lines i.e. is [2,0] and [2,2]. The lines are drawn again covering row 0, row 2, and column 2. The lines still are still 3 and do not equal to the number of developers which is 4.

The matrix illustrates subtracting the smallest uncovered value and adding it at line intersections. section 3.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines uncovered entries and applies them in two matrix adjustments to expose enough zeros for assignment.
Examples
Traces a four-developer, four-module matrix through uncovered values of 2 and 1 until four lines cover the zeros.
What you can do after
Apply it by finding the smallest uncovered value, subtracting it from uncovered entries, and adding it at line intersections.
How it connects
Connects uncovered entries to the Hungarian algorithm, cost matrices, zero-covering lines, and one-to-one assignment.

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.