15-451/651 MINI #5: due 11:59pm Tues Nov 12, 2013 ========================================================================= 1. The Max-coverage problem is similar to the Set Cover problem, but with a small difference. As in Set Cover, you are given a universe X of n elements, and subsets S_1, S_2, ..., S_m. You are also, however, given an integer K. You want to pick K sets such that their union is as large as possible. Here is a natural greedy algorithm: Pick the set that covers the most yet-uncovered elements. Repeat until K sets are picked. Show that the greedy algorithm gives a (1-1/e)-approximation. I.e., if there is a collection of K sets that can cover T elements, then the greedy algorithm finds K sets that cover at least T(1-1/e) elements. 2. For vertex cover we mentioned the following algorithm in class: Pick an edge e. If it is not covered yet, pick a *random* endpoint of this edge and add it to the cover. Then discard the edge. Repeat. a) Consider a star graph. This has a vertex cover of size 1 (the center node). Show that the expected number of vertices picked by the algorithm when run on the star graph is at most 2. b) If a graph has a vertex cover of size T, show how its edges can be colored using T colors so that the edges of each color class look like a star. c) On any graph G, prove that the expected size of the vertex cover output by the randomized algorithm above is at most 2*OPT.