CS614. Advanced Algorithms. L10 Quiz.

CS614. Advanced Algorithms.

L10 Quiz

Back to the course page

Problem 1. Set Cover: The Greedy Bound is Tight

We argued in class that the greedy approach to solving the unweighted Set Cover problem achieves an approximation ratio of O(H_n). Argue that this bound is tight, i.e, come up with examples where the algorithm picks sets in a manner that the cost of the solution is roughly H_n worse than optimal.

Problem 2. Set Cover and Related Problems

1. Show that Vertex Cover is a special case of Set Cover.

2. Also show that Dominating Set and Set Cover are equivalent (i.e, Set Cover can be reduced to Dominating Set and vice versa).