Solution to a Np-hard problem and its relevance to a dual LP

Question

From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual):

Let $y^*$ be an optimal solution to the following dual LP $$max \sum_{i=1}^n{y_i}$$$$subject \sum_{i:e_i\in{S_j}}{y_i \leq w_j}, y_i \geq0; j=1,...,m;i=1,...,n$$ and consider the solution in which we choose all subsets for which the corresponding dual inequality is tight; that is, the inequality is met with equality for subset $S_j$, and $\sum_{i:e_i \in{S_j}}{y^* = w_j}$. Let $I^{'}$ denote the indices of the subsets in this solution. We will prove that this algorithm also is an $f$-approximation algorithm for the set cover problem

I would like to know what does the writer mean by corresponding dual inequality? Is there any correspondence between a solution of the Set Cover problem and a dual LP solution?

I can't understand what does the paragraph mean.

Thanks in advance.

Answer 1

Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as complementary slackness are satisfied by any pair of optimal solutions.

In this case, however, we are already looking at the dual linear program; the constraints here correspond to subsets. In detail, the constraint $\sum_{i\colon e_i \in S_j} y_i \leq w_j$ corresponds to the subset $S_j$.

What is the relation to Set Cover? There is a natural linear program which is a relaxation of a natural integer programming formulation of Set Cover. If you compute its dual, you get the linear program that you quote. (If you're not sure which primal linear program was used to generate this dual linear program, you can always compute the dual of the dual linear program to get back the primal linear program.)