# Approximate LP for vertex cover problem

I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $$OPT$$. I do not understand why the approximate solution $$\sum_u w_u x^*_u \leq OPT$$

where $$w_u$$ is the weight to each vertex and $$x^*_u$$ is the approximate solution to the vertex cover problem and $$0 \leq x_u^* \leq 1$$

Can someone provide an explanation on how it is possible for the equation above ?

\begin{align} &\min \sum_{v \in V} x_v \\ \text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\ & x_v \in \{0,1\} &&\text{for every } v \in V \end{align} Here $$V$$ is the set of vertices and $$E$$ is the set of edges.

The optimal solution for this integer program is the minimum vertex cover in the graph. We denote its value by OPT.

Unfortunately integer programming is NP-hard to solve exactly, so we consider a linear programming relaxation, replacing the constraint $$x_v \in \{0,1\}$$ by the constraint $$x_v \in [0,1]$$:

\begin{align} &\min \sum_{v \in V} x_v \\ \text{s.t.}\;\; & x_u + x_v \geq 1 &&\text{for every } (u,v) \in E \\ & 0 \leq x_v \leq 1 &&\text{for every } v \in V \end{align}

Every feasible solution of the original integer program is also a feasible solution of the linear programming relaxation. In other words, the linear program is minimizing over a set of solutions which contains the set of solutions to the integer program. Therefore the optimal value of the linear program is bounded from above by OPT.

More abstractly, if $$A \subseteq B$$ then $$\min_{x \in B} \phi(x) \leq \min_{x \in A} \phi(x).$$ In our case, $$A$$ is the set of solutions to the integer program, $$B$$ is the set of solutions of the linear program, and $$\phi$$ is the objective function $$\sum_{v \in V} x_v$$.

• shouldn't the optimal solution to the LP be worse than the optimal vertex cover because the vertex set it generates is an approximation to the problem ? Commented Nov 27, 2020 at 13:43
• The LP is optimizing over a larger set of potential solutions, so it can only find a better solution than the IP. Commented Nov 27, 2020 at 13:51