moed A - set cover approx.

[Tom]

Can someone provide an explanation for the set cover approximation
algorithm in the last exam?

Thanks!


(btw - thanks to everyone who answered my questions so far :-) )

[Ofir]

You go over all items and for each item you take the (at most) 7
groups (sets) it is in.
The optimum is to take just one set of those seven, so by taking all
of them you actually approximate within a constant factor, 7.

[roye]

Ofir, did you get full credit for this answer?

On Jul 24, 4:46 pm, Ofir <ofir.isr...@gmail.com> wrote:
> You go over all items and for each item you take the (at most) 7
> groups (sets) it is in.

> The optimum is to take just onesetof those seven, so by taking all

[Ofir]

I actually heard this answer (which seems correct..) from Adi right
after the exam. I didn't write this.
Did you find any problem with it?

[roye]

I'm trying to figure that out; it just seems too simple. If you
google approximations of this algorithm you find either ln (n)
approximation factors or something like 1 + 1/2 +1/3 ... + 1/k where k
is the set of the largest set (I think). I'm not sure how you include
the 7 property with these though...

[Adi Glucksam]

what you should do is:

(1) take one element randomly.

(2) take all the subset it belongs to (max 7)

(3) remove form your list all the elements that are already coved by the set you have.

(4) redo 1-4 on the elements left on your list. if your list is empty, stop & return the subsets you've collected.

because of the way the algorithm is defined it is clear that our final cover will cover the whole set.

let Si1,Si2,...Siopt the real set cover.

for each Sij if the'res an element in it such that it was randomly chosen, then it has 7 sets in the set cover. otherwise it has less.

hence |your cover|<=7*|optimal cover|

Adi Glucksam

[roye]

thanks Adi

[Tom]

another good way to see the 7-approximation is to take an "extreme"
scenario:
imagine you have the following groups:

{1}, {1}, {1}, {1}, {1}, {1}, {1}, {2}, {2}, {2}, {2}, {2}, {2}, {2},
{3}, .... etc.

The optimal solution will take one of each.

Our approximation takes everything.

[roye]

Right, in this case the ordinary greedy algorithm does better.
Basically, for any graph where n < e^7 (by the lg n result I quoted
above) it does better.
By "ordinary greedy" i mean pick the set that adds the highest
proportion of uncovered elements at each step (the analysis is shown
here: http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture02.pdf)