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

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

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