4
$\begingroup$

Let us be given a $n\times n$ matrix containing only zeros and ones.Now, the goal is to remove some 'ones' from the matrix (i.e. replace them with zeros) so that in each row and each column there is at most one 'one'. Of course, it is preferable that we leave as much 'ones' as it is possible (maximum is obviously $n$).

Now, let us define the following algorithm: if there is a 'one' which is all alone in a column or a row, leave it there, and replace all 'ones' in its column and row with zeros. We repeat the process as long as there are single 'ones' in rows or columns. If there are no single 'ones' left, we take the first row or column (first is counted from up (for rows) and from left (for columns)) containing two 'ones' (if there are no pairs, we go for the first triplet and so on). In that pair (or triplet, or ...) we leave the first 'one' intact (first is counted from the left for elements of row, from the top for elements of a column) and change all other 'ones' in the row and column of that first 'one' into zeros. Now, we check are there now any single 'ones' as defined above - if yes, we repeat that part of the algorithm, if no, we look for the first pair, triplet, etc. The algorithm ends when all 'ones' are singles both in their column and row.

Does this algorithm always give the maximum covering, i.e. does it always terminate with maximal number of 'ones' in the final matrix? In other words, can there be a matrix with a possible exclusion of some ones such that it ends up with $n$ ones using some other exclusion scheme, while ending up with less than $n$ 'ones' using the algorithm described above?

3 Answers 3

3

Diagram to give an example for deinst's answer. I tried putting this in a comment, but it stuffed up the formatting. The Xs marks ones that give a complete match

X01100001 1X1100000 11X100000 111X00000 00001011X 0000X1110 000011X10 0000111X0 01000X000 

Now, suppose we take the two squares marked by Y's

*0**0000Y 111100000 111100000 111100000 00001011* 00001*110 00001*110 00001*110 0*000Y000 

We have two 3 by 4 squares left, so we can take 6 more items. This give a total of 8 instead of 9. We can enforce those two blocks to be taken by using a permutation.

5

I'm not sure about whether this works, but I'd be doubtful.

Another way to express this problem is finding maximum partial matchings in a bipartite graph. (Just interpret the matrix an adjacency matrix for the graph). By a maximum partial matching I mean a maximal-sized set of edges no two having a vertex in common.

The reason for my scepticism is that if your algorithm worked, then it would give an algorithm for finding the solution in the situation of Hall's marriage theorem. Your algorithm is "monotone" in the sense that it adds edges but never removes them, but all the algorithms I have seen for Hall's theorem, one needs to remove edges in certain circumstances in the process.

For the problem is hand, an algorithm comes from any that solves the maximum flow problem in a network. Attach a source to each vertex on one side of the bipartition and a sink to each vertex on the other side. Give all edges unit capacity and find a maximum flow.

5

Yes. Consider a large square matrix with two large square blocks filled with ones and one empty row and one empty column. Delete one one from each of the blocks off the diagonal, and place a corresponding one in the empty row and column. You now have one row with two elements, the rest having many elements, and one column having only two elements, the rest having many. Your procedure will deal with the sparesely populated row and column first. Permute the rows and columns so that you procedure links the two choices with different blocks. Now the remainder of each block has one more row than it has columns or vice versa, as a perfect matching cannot exist. It is easy to see however that a perfect matching existed before your algorithm matched the sparse row and column.