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