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

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.

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$.
• Thank you very much. The writer says and consider the solution in which we choose all subsets for which the corresponding dual inequality is tight, what does he mean by solution and what is this solution relevance to $y^*$? Is this a solution (feasible) to Dual LP? From what I understand, what he means by solution is to take the $y^*$ and then consider the sets for which the constraint is equality not inequality. Am I right? – M a m a D Mar 9 '16 at 10:16
• By a solution, the authors mean a solution to Set Cover. You choose the solution using an optimal solution $y^*$ for the dual linear program. In short, you get a solution to Set Cover from an optimal solution for the dual LP. – Yuval Filmus Mar 9 '16 at 11:03