[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: algorithm for reducing rows/columns
From: |
Kim Hansen |
Subject: |
Re: algorithm for reducing rows/columns |
Date: |
Mon, 20 Dec 2010 00:16:19 +0100 |
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.
--
Kim Hansen
Vadgårdsvej 3, 2.tv
2860 Søborg
Phone: +45 3091 2437