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
