# Problems on Approximation Algorithms

- 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$.)
- 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^*|$.)
- 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).
- Give a simple 3-approximation for the unweighted problem.
- Show that local search can give 2-approximation
- Give a 3-approximation for the weighted version.

* Last updated 5 March 2013*