2 of 19

SET-COVER

Instance: a finite set X and a family F of subsets of X, such that

Problem: to find a set C⊆F of minimal size which covers X, i.e –

Problem is NP-hard

3 of 19

SET-COVER: Example

4 of 19

The Greedy Algorithm

C ← φ
U ← X
while U ≠ φ do

select S∈F that maximizes |S∩U|
C ← C ∪ {S}
U ← U - S

return C

5 of 19

Demonstration

compare to the optimal cover

6 of 19

How Good of an Approximation?

We’d like to compare the number of subsets returned by the greedy algorithm to the optimal
The optimal is unknown, however, if it consists of k subsets, then any part of the universe can be covered by k subsets!
Which is exactly what the next 3 distinct arguments take advantage of

7 of 19

Loose Ratio-Bound

Claim: If ∃ cover of size k, then after k iterations the algorithm covered at least ½ of the elements

Suppose it doesn’t and observe the situation after k iterations:

the n elements

already covered

>½n

8 of 19

Loose Ratio-Bound

Claim: If ∃ cover of size k, then after k iterations the algorithm have covered at least ½ of the elements

the n elements

Since this part → can also be covered by k sets...

already covered

>½n

9 of 19

Loose Ratio-Bound

Claim: If ∃ cover of size k, then after k iterations the algorithm have covered at least ½ of the elements

the n elements

there must be a set not chosen yet, whose size is at least ½n·1/k

already covered

>½n

10 of 19

Loose Ratio-Bound

Claim: If ∃ cover of size k, then after k iterations the algorithm have covered at least ½ of the elements

the n elements

already covered

>½

Thus in each of the first k iterations we’ve covered at least ½n·1/k new elements

and the claim is proven!

11 of 19

Loose Ratio-Bound

Claim: If ∃ cover of size k, then after k iterations the algorithm covered at least ½ of the elements.

Therefore after klogn iterations (i.e - after choosing klogn sets) all the n elements must be covered, and the bound is proven.

12 of 19

Better Ratio Bound

Let S₁, …, S_t be the sequence of sets outputted by the greedy algorithm. Let, for 0 <= i <= t��

Since, for every i, U_i can be covered by k sets, it follows��

13 of 19

Better Ratio Bound

�

Hence, for any 0 <= i < j <= t��

Which implies that for every i��

Therefore, t <= k ln(n) + 1

14 of 19

Tight Ratio-Bound

Claim: The greedy algorithm approximates the optimal set-cover to within a factor

H(max{ |S|: S∈F } )

Where H(d) is the d-th harmonic number:

15 of 19

Claim’s Proof

Charge $1 for each set

Split cost between covered elements

Bound from above the total fees paid

0.2

each recipient pays the fractional cost for the first set it appears in

16 of 19

Analysis

Thus, every element x∈X is charged

��

Where S_i is the first set that covers x.

17 of 19

Lemma

Lemma: For every S∈F��

Proof: Fix an S∈F. For any i, let��

∀1≤i≤k : S_i covers u_i-1-u_i elements of S�

Let k be the smallest index, s.t. u_k=0

number of members of S still uncovered after i iterations

18 of 19

Lemma

sum charges

definition of u_i-1

Telescopic sum

H(u_k)=H(0)=0�

H(u₀)=H(|S|)

Si covers more than S or else the greedy strategy would have taken S instead of S_i

19 of 19

Analysis

Now we can finally complete our analysis: