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

- 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*x*0. Prove that this algorithm gives an_{S}>*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. - 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. - 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? - 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. - Read the paper

David Kempe, Jon Kleinberg, Éva Tardos: Maximizing the
Spread of Influence in a Social Network. In Proceedings of KDD 2003,
Washington DC.

- Read the paper

__Energy-efficient
Broadcast in Wireless Ad-hoc Networks: Lower bounds and Algorithms__. F. Bian, A. Goel, C. Raghavendra, and X.
Li. Journal of Interconnection Networks, 3(3-4), September & December 2002,
pages 149-166.

- Write a
**very brief**summary of either 5 or 6, focusing on the use of the greedy technique. You may study these papers in groups and even have one person read and present a paper to a group, but you must write the summary yourself.