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