Set Cover Problem Approximation Techniques

Approximating the Set Cover problem

The problem presented as a problem in bipartite graphs Elements 2 1 3 4 Sets

1 and 3 are together a Set Cover Minimum size Set Cover: size 2. NPC problem. Elements 1 3 Sets

The dual fitting of Lovasz for Set Cover When my supervisor saw this paper with countless inequalities he took a look and said: Chinese! Today I can say: Trivial. My presentation has no inequality. Almost not needed. Why did Lovast wrote it this way: this is what geniuses do.

The LP primal Minimize xS Subject to S | e SxS 1 xS 0

The LP Dual Maximize ye Subject to e | e SyS 1 ye 0

Explaining the dual The dual says: put values of elements so that the total sum of fractions on the elements of a set is at most 1. If you think of integral solutions it makes sense.

The greedy algorithm Say that we cover some elements. Let SR be the elements in S that are still uncovered. 1. While there are uncovered elements 1.1 chose the largest size SR and add it into the solution C 2. Return C.

Giving dual values to elements Say greedy chose SRthat covers k elements. Give each element in the star value 1/k. Note that for the set SR in question the dual inequality of at most 1 holds (with equality). What about other stars? They have edges to the elements that got value 1/k now. The inequality does not hold at all for other stars.

The greedy star and others. Note that the set selected costs 1 And the dual was increased by one. Thus we keep having dual value which equals the number of sets added by greedy. It can not be that all dual constrains hold. The problem is NPC.

The greedy algorithm and an arbitrary star 11/15 /1 1/15 1/15 1/1/15 5 11/15 /1 Our star has 15 elements. So the largest star has at least 15 elements. The intersection is on 4 elements. The largest value they can get is 1/15. Thus the values

The greedy algorithm and an arbitrary star 1/13 1/1511/12 /1 1/1/15 5 11/14 /1 The above replacement can only increase the dual.. Thus the values the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/11 1/11 1/11 1/11 1/13 1/1511/12 /1 1/1/15 5 11/14 /1 Our star has length 11 so the greedy star is at least 11 hence the dual values at most 1/11Thus the values the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/1/15 5 11/14 /1 The increase above only makes the dual largerthevalues the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/1/15 5 11/14 /1 The increase above only makes the dual largerthe values the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/7 1/1/15 5 11/14 /1 1/7 The remaining star had size 7. The greedy is at least as large. Hence the values of the dual is at most 1/7values the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/6 1/1/15 5 11/14 /1 1/5 The above change only increases the dual.aluehe mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/4 1/6 1/1/15 5 11/14 /1 1/5 1/4 The star that remains has size 4, and so the greedy at least 4 and so the dual values are al most . the mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/3 1/6 1/1/15 5 11/14 /1 1/5 1/4 The above change only increases the dualhemutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/3 1/6 1/1/15 5 11/14 /1 1/5 1/4 1/2 1/2 Our star is size 2 now, and so the greedy is at least 2. The dual values at most 1/2mutual elements get is at most

The greedy algorithm and an arbitrary star 1/10 1/9 1/11 1/8 1/13 1/1511/12 /1 1/7 1/3 1/6 1/1/15 5 11/14 /1 1/5 1/4 1/2 1 The increase above only makes the dual larger.mutual elements get is at most

The sum of elements of a set This sum is Hd Let be the largest degree. The sum is at most H Divide every dual value by H We get a dual feasible solution which is at most the opt fractional dual which equals the opt fractional primal which is at most the minimum size Set-Cover.

The sum of elements of a set Thus Greedy-dual/H is a dual feasible solution, is at most opt. Recall that the number of sets the greedy algorithm chose equals the Greedy-dual cost. Let Gr be the cost of Greedy. Gr H opt. H is at most ln +1. We do not get ln n but rather ln of max degree which could be much better.

A remarkable results Dinur et al. Approximating within better than 0.999999999 ln n is as hard as solving exactly, namely is an NP-hard. This is one of many problems for which we have an upper bound that equals the lower bound. For an easy example check the k- Center problem.

An example for which the ratio is indeed log n v1 v2 a b c n/2 n/4

Explaining the Set Cover instance What is inside the rectangle are the elements. The set a contains the upper 1/3 elements. The set b contains the middle third of elements. The set c contains the lower third part of the elements. The set v1 contains the elements (the ones below it). v2 contains of the rest of the rest of the elements Similarly for v3,v4 etc.

In the greedy algorithm, opt=3 Note that the optimum here is 3. All the elements can be covered by {a,b,c}. However v1 is joined to n/2 elements and will be chosen by the greedy rule: n/2>n/3. This cuts the number of elements into half. But forgetting that, v2 contains of the remaining elements and a again a third of what remains and so on. So the greedy algorithm chooses v1, and then v2 and so on. About log2n sets instead of 3. Note that throughout, opt=3. The optimum does not go down!