On Sun, Dec 19, 2010 at 6:16 PM, Kim Hansen <address@hidden> wrote:
On Sun, Dec 19, 2010 at 03:36, Mike Miller 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.
a=[0 1 1 1 0 0 0
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0 ]
q=sum(a)
[x ix]=max(q)
[s t]=sortrows(a,-ix)
b=s'
q=sum(b)
[x ix]=max(q)
[s1 t]=sortrows(b,-ix)
s11=s1'