<p>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}$.</p>

<p>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</p>

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

<p>Next, we relax the ILP $(2)$ to a linear program.</p>

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

<p>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 &lt; \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:</p>

<p>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</p>

<p>$\displaystyle \sum_{v\in S} c(v)$</p>

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

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

<p>$\displaystyle = 2\cdot opt(LP)$</p>

<p>$\displaystyle \leq 2\cdot opt(VC)$</p>

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

<p><strong>Question:</strong></p>

<p>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 &gt;= 1/3$ then $x_v=1$ and if $x_v &lt; 1/3$ then $x_v=0$, our approximation bound would be $3$.</p>

<p>My question is how to find and show that the rounding we pick is optimal?</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2013-03-21T21:26:50.463Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-03-21T22:01:45.903Z
How do we know that 1/2 is good? How do we show it? Thanks in advance!
IvanJ
CC BY-SA 3.0
2013-03-21T23:22:32.760Z
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
Suresh Venkat
CC BY-SA 3.0
2013-03-22T03:41:06.773Z
_Let us apply the methodology described in the first section._ — The first section of what?
Jeffε
CC BY-SA 3.0
2013-03-23T05:06:17.917Z
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.
Chandra Chekuri
CC BY-SA 3.0
2013-03-26T05:51:10.703Z
Thank you for all good comments! I appreciate it! You chose to rounding variables >= 1/2 because that is the smallest threshold that guarantees that the covering constraints will be satisfied. I think I got it. Is there a way to give you points somehow? I'm new to stackexchange.
IvanJ
<ds.algorithms><linear-programming><integer-programming>
How to determine proper rounding in linear programming relaxations?
IvanJ
# How to determine proper rounding in linear programming relaxations?

(Asked by: username_0 on 2013-03-21)

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!

**Tags:** ds.algorithms, linear-programming, integer-programming

> **Comments:**
> **username_1**: 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.  
> **username_0**: How do we know that 1/2 is good? How do we show it? Thanks in advance!  
> **username_1**: 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  
> **username_2**: _Let us apply the methodology described in the first section._ — The first section of what?  
> **username_3**: 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.  
> **username_0**: Thank you for all good comments! I appreciate it! You chose to rounding variables >= 1/2 because that is the smallest threshold that guarantees that the covering constraints will be satisfied. I think I got it. Is there a way to give you points somehow? I'm new to stackexchange.  

---

## 0 answers

