Problems on Approximation Algorithms

1. Use randomized rounding to give a $3\log n$-approximation of the (weighted) Dominating Set problem.
(Hint: First, formulate the straightforward integer program. Then round it and select a vertex $v$ with probability $x^*_v \cdot 3\ln n$, where $x^*_v$ is the LP-value of the indicator variable for vertex $v$.)
2. Show that the following randomized algorithm gives a 2-approximation for the Vertex Cover problem:
While there is an uncovered edge $(u,v)$ do: Add $u$ ($v$) to the cover $C$ with probability $1/2$.
(Hint:Suppose we continue the algorithm until it contains all the nodes of an optimal vertex cover $C^*$; show that the expected number of steps that happens is at most $2|C^*|$.)
3. Consider the 3-Set Packing problem. Given is a collection of sets of size 3; find a subcollection of disjoint sets of maximum cardinality (or weight).
1. Give a simple 3-approximation for the unweighted problem.
2. Show that local search can give 2-approximation
3. Give a 3-approximation for the weighted version.

Last updated 5 March 2013