On Sun, Dec 19, 2010 at 03:36, Mike Miller <address@hidden> wrote:
This is probably more of a mathematical question than an Octave
question, per se, but someone here might be interested...
Here's the problem, in a simple form: I have a square symmetrix
matrix, M, with all elements either zero or one. All diagonal elements
are zero. I want to find a set of indices, I, such that M(I,I) is a
zero matrix of the largest possible size. There will usually be more
than one I that maximizes size(M), but they are all equally good for my
purposes, so I would choose one arbitrarily. Maybe if I always delete
one of the rows/cols with the largest number of ones, and repeat, that
will do it, but I'm not sure of that. Any ideas?
This simple example shows that the greedy approach is not optimal:
0111000
1000100
1000010
1000001
0100000
0010000
0001000
The greedy approach will start by deleting row 1 first because of the 3
ones, and then it has to delete 3 other rows. The optimal solution is to
delete rows 2, 3 and 4 as that will clean up row 1.
I think your problem is identical to
http://en.wikipedia.org/wiki/Maximum_clique where you have a node for
each row and a connection for each 0. Then the maximum clique is the
rows you want to keep.
This means that your problem is NP-Complete, and that means it is hard
to find the optimal solution. You might want to use the greedy approach
if the suboptimal solution is good enough.