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? Lets 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 thats 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!
How to determine proper rounding in linear programming relaxations?
ds.algorithms;linear programming;integer programming