help-octave
[Top][All Lists]
Advanced

[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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]