# Primal-dual schema in approximation algorithms

I was studying Set Cover via the Primal–Dual Schema on my own that I faced a problem in the following paragraph: Consider an LP-relaxation for an NP-hard problem. In general, the relaxation will not have an optimal solution that is integral(why?? when we relax an LP we can choose the variables from the interval of [0,1] so the solution must be integral!!!). Does this rule out a complementary slackness condition driven approach? Interestingly enough, the answer is ‘no’. It turns out that the algorithm can be driven by a suitable relaxation of these conditions!(what this paragraph tries to say, I don't get the concept of relaxation here, why we do it??) I apologize for my long question, I really appreciate if anybody can help me.

• The usual rule is one question per post. – Yuval Filmus Jul 8 '17 at 22:38

The answer to the first question is that in linear programming we cannot enforce the variables to be integers. Therefore the optimal solution could be fractional. Consider for example the vertex cover problem for a graph $G = (V,E)$:
\begin{align*} &\min \sum_{v \in V} x_v \\ s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\ & x_v \in \{0,1\} \end{align*}
\begin{align*} &\min \sum_{v \in V} x_v \\ s.t. \quad& x_u + x_v \geq 1 \text{ for all } (u,v) \in E \\ & 0 \leq x_v \leq 1 \end{align*}
Now take the case of the triangle. The smallest vertex cover has size 2, but the optimal solution for the LP is $(1/2,1/2,1/2)$. As you can see, it isn't integral.