Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Optimizing a set-cover like algorithm

Subject: Optimizing a set-cover like algorithm

From: Johannes Korsawe

Date: 8 Sep, 2009 07:53:02

Message: 1 of 1

Dear community,

today, i have a - hopefully interesting - problem of algorithmic optimization.

I have n positions of a cubicle. If you plot all cubicles over another, each cubicle can be seen from outside, maybe just an edge, maybe just some small part of a corner.

Now lets think of a set of cubicle corner- and edgepoints and their n transformations. Of course, all of these points (the point-cloud) are (is) covered by the plotted cubicles. (This was the trivial part.)

Now, i want to reduce the number of cubicles, but still nearly (!) want to cover the same space. In other words, i want that the point-cloud of all n cubicles is nearly inside the remaining cubicles.

Now i somehow define a measure for the ratio of covering from one cubicle's points by another cubicles body. By using this measure, i compute a symmetric matrix A where

A(i,j) denotes the ratio, how well the cubicle in position i covers the points of cubicle in position j.

The better the covering, the smaller the value A(i,j). Due to this fact, the entries on the diagonal all equal to zero.

Now i want to prescribe a tolerance tol and want to find the minimal set of cubicles, so that the covering of all n cubicles' points has a ratio of at most tol. To this end, i wrote the following algorithm. (You should mentally identify the rows with the positions of cubicles that should be reduced and the columns with the points of the positions that shall still be nearly covered.)

% for meaningful use of min/max i need a copy of A
B=A; alldistances=distances;
for i=1:n,A(i,i)=1e4;end

% start by keeping all positions
keep=true(1,n);

reduced=1;
while reduced==1,
    reduced=0;
    I=find(keep);
    tmp_A=A(keep,:);tmp_B=B(keep,:);
    % find positions that are inside tolerance
    nerd=min(tmp_A,[],2);JJ=find(nerd<tol);
    for k=1:length(JJ),
        J=JJ(k);
        % What would happen if deleting position J ?
        test=tmp_B([[1:J-1],[J+1:end]],:);
        if max(min(test,[],1))<tol,
           % maximal distance of nearest point sets is still smaller than tolerance
            reduced=1;
            keep(I(J))=false; % position I(J) can be deleted
            break;
        end
    end
end

index_list=find(keep);

The algorithm works as described above. BUT it needs a lot of time, as the line

test=tmp_B([[1:J-1],[J+1:end]],:);

needs a lot of time and may be called often (as it is inside the k-loop).

My question to you, humble community, is, if you have some ideas to accelerate the algorithm above.

Thanks in advance,
Johannes Korsawe

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us