2
$\begingroup$

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.

Improve this question
$\endgroup$
3
$\begingroup$

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.)

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – M a m a D Mar 9 '16 at 10:16
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 9 '16 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.