|
From: | Doug Stewart |
Subject: | Re: algorithm for reducing rows/columns |
Date: | Sun, 19 Dec 2010 21:05:44 -0500 |
On Sun, Dec 19, 2010 at 03:36, Mike Miller <address@hidden> wrote:This simple example shows that the greedy approach is not optimal:
> 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?
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.
--
Kim Hansen
Vadgårdsvej 3, 2.tv
2860 Søborg
Phone: +45 3091 2437
_______________________________________________
Help-octave mailing list
address@hidden
https://www-old.cae.wisc.edu/mailman/listinfo/help-octave
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'
[Prev in Thread] | Current Thread | [Next in Thread] |