algorithmapproximationset-cover

An example of an input to the set cover problem which does not provide a 2-approximation


I need some help with the following question:

Show an example of an input to the set cover problem for which the greedy algorithm shown in class does not provide a 2-approximation.

The greedy algorithm:

X - a finite set

F - family of subsets of X such that the union gives X

C - the desired set of minimal size which covers X.

ctur


Solution

  • There is a 3/2 approximation example in the wikipedia page presenting the greedy algorithm for the set cover problem.
    We can see two groups of sets composing F. 2 sets (the 'lines'), forming a partition, each of them with half of the 'points'. And 3 other sets (the 'rectangles'), forming another partition, with resp. 2, 4 and 8 points.
    The greedy algorithm will choose the 'rectangles' since it starts with the largest set of F.
    It is possible to adapt this scheme to make a 'worse' approximation, to 'trick' the greedy algorithm.
    Recipe: draw the same figure, but with a 31 x 2 grid instead of a 7 x 2. Keep the two lines with half the points in each (still forming a partition), and add two 'rectangles' (the two biggest, they will have resp. 16 and 32 'points') on the right side. The greedy algorithm will return the 5 'rectangles', while the optimal solution will consist of the two lines, so an approximation of 5/2 > 2.

    Note that this process can be extended infinitly (with a (2^n)-1 per 2 grid), so you can prove that the greedy algorithm for the set cover is not a k-approximaation, for any number k.