While I had the dissertation I needed for the last problem, and before I had to send it back (without making copies), I skipped ahead to another problem that used it as a reference.
The problem: Consecutive Ones Matrix Augmentation. This is problem SR16 in the appendix.
The description: Given an mxn matrix of 0’s and 1’s and a positive integer K, can we change K or fewer 0’s into 1’s to give the matrix the consecutive ones property. See the Consecutive Ones Submatrix problem for more detail on this property.
Example: Here is the matrix that did not have the property from last week:
Recall that we’re looking for a way to permute the columns so that there are no gaps in the 1’s in each row. The easy solution here is to add a 1 in the second row (making it all 1’s). In that case, the matrix has the consecutive ones property without needing any column permutations.
Reduction: Again, it is found in the dissertation by Booth, but this time uses Optimal Linear Arrangement. Recall in that problem we were given a graph and needed to find an ordering of vertices to minimize the “score” of the differences of the ordering values.
The corresponding idea here is to start with the graph and build an incidence matrix, just like in the Consecutive Ones Submatrix problem. We notice that any permutation of the rows (in the dissertation, you permute the rows to find consecutive ones in each column) corresponds to a permutation of the vertices in the OLA problem. If we took a permutation of the vertices, each edge (column) of the incidence matrix has exactly two 1’s in it. There may or may not be any 0’s between those ones, but if there are, we can convert those 0’s into 1’s (this is the augmentation).
The way these problems relate is that if an edge exists between two vertices, vi and vj, located at positions i and j in the final permutation, that edge adds j-i to the cost (assuming j > i). In our matrix, if we permute the row corresponding to vertex vi to row i, and permute the row corresponding to vertex vj to row j, then there are j-i-1 o’s between the two rows. So we could set them all to 1, and that column would have the consecutive ones property.
Thus, a solution of cost K to the OLA problem corresponds to a solution to the Consecutive Ones Matrix Augmentation problem of cost K-|E|, since there are |E| columns in the incidence matrix, and each one differs by 1 from the OLA cost of the edge.
Difficulty: 6, mainly because of the incidence matrix/adjacency matrix difficulty I talked about last time, but also because OLA is not easy to get. If you’ve already shown them incidence matrices (for example, because you’ve gone over the Consecutive Ones Submatrix problem), then this is probably a 4.