4
$\begingroup$

Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such that for every ${(u,v)\in E}$ at least one of ${u}$ or ${v}$ belongs to ${S}$.

Let us apply the methodology described in the first section. Given a graph ${G=(V,E)}$ and vertex costs ${c(\cdot)}$, we can formulate the minimum vertex cover problem for ${G}$ as an ILP by using a variable ${x_v}$ for each vertex ${v}$, taking the values $0$ or $1$, with the interpretation that ${x_v=0}$ means that ${v\not\in S}$, and ${x_v=1}$ means that ${v\in S}$. The cost of the solution, which we want to minimize, is ${\sum_{v\in V} x_v c(v)}$, and we want ${x_u+x_v \geq 1}$ for each edge ${(u,v)}$. This gives the ILP

$\displaystyle \begin{array}{lll} {\rm minimize} & \sum_{v\in V} c(v) x_v \\ {\rm subject\ to} \\ & x_u + x_v \geq 1 & \forall (u,v) \in E\\ & x_v \leq 1 & \forall v\in V\\ & x_v \in {\mathbb N} & \forall v\in V \end{array} \ \ \ \ \ (2)$

Next, we relax the ILP $(2)$ to a linear program.

$\displaystyle \begin{array}{lll} {\rm minimize} & \sum_{v\in V} c(v) x_v \\ {\rm subject\ to} \\ & x_u + x_v \geq 1 & \forall (u,v) \in E\\ & x_v \leq 1 & \forall v\in V\\ & x_v \geq 0 & \forall v\in V \end{array} \ \ \ \ \ (3)$

Let us solve the linear program in polynomial time, and suppose that ${{\bf x}^*}$ is an optimal solution to the LP $(3)$; how do we “round” it to a $0/1$ solution, that is, to a vertex cover? Let’s do it in the simplest possible way: round each value to the closest integer, that is, define ${x'_v = 1}$ if ${x^*_v \geq \frac 12}$, and ${x'_v = 0}$ if ${x^*_v < \frac 12}$. Now, find the set corresponding to the integral solution ${{\bf x}'}$, that is ${S:= \{ v : x'_v = 1 \}}$ and output it. We have:

The set ${S}$ is a valid vertex cover, because for each edge ${(u,v)}$ it is true that ${x^*_u + x^*_v \geq 1}$, and so at least one of ${x^*_u}$ or ${x^*_v}$ must be at least ${1/2}$, and so at least one of ${u}$ or ${v}$ belongs to ${S}$; The cost of ${S}$ is at most twice the optimum, because the cost of ${S}$ is

$\displaystyle \sum_{v\in S} c(v)$

$\displaystyle = \sum_{v\in V} c(v)x'_v$

$\displaystyle \leq \sum_{v\in V} c(v)\cdot 2 \cdot x^*_v$

$\displaystyle = 2\cdot opt(LP)$

$\displaystyle \leq 2\cdot opt(VC)$

And that’s all there is to it! We now have a polynomial-time 2-approximate algorithm for weighted vertex cover.

Question:

I realize that depending on what we pick as our rounding point, that is what our approximation bound is going to be. Therefore since we picked $1/2$ as our rounding point, approximation bound is $2$. If we picked $1/3$ as our rounding point, meaning if $x_v >= 1/3$ then $x_v=1$ and if $x_v < 1/3$ then $x_v=0$, our approximation bound would be $3$.

My question is how to find and show that the rounding we pick is optimal?

Thanks in advance!

$\endgroup$
  • 4
    $\begingroup$ Often it depends on the problem. If there's a convenient parameter that describes the rounding, then you write the approximation ratio in terms of this parameter, and then optimize it. In this case, the ratio you get is $1/\rho$, where $\rho$ is the threshold and we know that $\rho \le 1/2$. Optimizing yields the answer. $\endgroup$ – Suresh Venkat Mar 21 '13 at 21:26
  • $\begingroup$ How do we know that 1/2 is good? How do we show it? Thanks in advance! $\endgroup$ – IvanJ Mar 21 '13 at 22:01
  • 2
    $\begingroup$ I don't know what "good" means. you want to minimize $1/\rho$, so you maximize $\rho$ subject to the constraints. If you're asking whether there's some other LP that can be rounded to a value better than 2, that's a different question altogether $\endgroup$ – Suresh Venkat Mar 21 '13 at 23:22
  • 2
    $\begingroup$ Let us apply the methodology described in the first section. — The first section of what? $\endgroup$ – Jeffε Mar 22 '13 at 3:41
  • $\begingroup$ The rounding depends on both constraints and the objective function. Here you chose to rounding variables >= 1/2 because that is the smallest threshold that guarantees that the covering constraints will be satisfied. Now suppose you consider a more general set covering problem where you are guarantees that each element is in at most k sets (for vertex cover k=2) then you would choose the threshold to be 1/k and get a k approximation. Note that this is not the only way to round. One can also use randomized rounding and many other methods. $\endgroup$ – Chandra Chekuri Mar 23 '13 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.