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.
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
.