# MS&E 319: Approximation Algorithms for Optimization Problems, Winter 2004-05

Instructor: Ashish Goel

Handout 2: Homework 1.

Given: 1/18/2005. Due: 1/27/2005.

You can collaborate with other students in this class to any extent, but under no conditions can you read another student’s answer or ask another person to write yours.

1. Consider the following approximation algorithm for the unweighted set-cover problem (i.e. all sets in the collection have the same cost): First, solve the fractional relaxation of the set cover problem optimally. Then choose all sets S such that xS > 0. Prove that this algorithm gives an f-approximation, where f is the maximum number of sets that can contain any one element (i.e. f is the the maximum frequency of an element). What does this imply for the vertex cover problem? Hint: Use complementary slackness.
2. In the class we saw that the greedy algorithm for maximizing submodular set functions gives a 2 approximation. Explain how that proof can be used as a black-box to obtain an O(log n) approximation guarantee for the greedy algorithm for unweighted set cover.
3. There exists a constant c > 1 such that no polynomial time approximation algorithm for the unweighted set cover problem gives an approximation ratio better than (log n)/c, unless P = NP. What bound does this give on the hardness of approximation for the problem of maximizing submodular set functions that we saw in class?
4. Consider the maximum independent set problem: given a graph G = (V,E), find the largest subset S of V such that there is no edge between any two vertices in S. Prove that the decision version of this problem in NP-complete. Hint: reduce from vertex cover.