Approximate LP for vertex cover problem
Let's start with an integer program for vertex cover:
\begin{align}
&amp;\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; &amp; x_u + x_v \geq 1 &amp;&amp;\text{for every } (u,v) \in E \\
&amp; x_v \in \{0,1\} &amp;&amp;\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}
&amp;\min \sum_{v \in V} x_v \\
\text{s.t.}\;\; &amp; x_u + x_v \geq 1 &amp;&amp;\text{for every } (u,v) \in E \\
&amp; 0 \leq x_v \leq 1 &amp;&amp;\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$.