Instructor: Ashish Goel
Handout 2: Homework 1.
1/18/2005. Due: 1/27/2005.
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
- 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.
- 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,
- Read the paper
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,
- 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