Primal-dual schema in approximation algorithms

Question

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.

• Yuval Filmus: The usual rule is one question per post.

Answer 1

You are asking many questions. I will only answer the first.

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*} $$

This is an integer program whose LP relaxation is

$$ \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.

• NedaHn: thank u for answering one of my questions, but my main question is about the relaxing part, I have really problem with that. even if it is a definition where this relaxation is used in primal-dual schema for set cover problem, just for proving approximation factor??
• Yuval Filmus: You should split your question to three different questions corresponding to the three different parts.