Consider Maximum-Coverage problem, which means there are set $A$ and $n$ subsets of $A$, we can choose $k$ subsets to cover some elements, and Maximum-Coverage is the assignment that cover most elements in $A$. We know by LP relaxation there is $1-1/e$ approximation algorithm, however, the integrality gap for it is $1-1/e+\epsilon$, which means there is an instance $I$ such that $LP(I)=1$ and $Opt(I)<1-1/e+\epsilon$, how to choose the problem set $I$?

  • $\begingroup$ What do you mean by $LP(I) = 1$? $\endgroup$
    – codeR
    Commented May 10 at 7:24
  • $\begingroup$ If the integrality gap is $1-\frac{1}{e} + \epsilon$, then by definition we have $LP(I) \ge \frac{OPT(I)}{1-\frac{1}{e} + \epsilon}$. $\endgroup$
    – codeR
    Commented May 10 at 7:27
  • $\begingroup$ What do you mean by "choose the problem set $I$"? Do you mean you want to find an instance (not problem set) where this bound is tight? $\endgroup$
    – codeR
    Commented May 10 at 7:29
  • $\begingroup$ Yes, I want to find a counterexample. $\endgroup$ Commented May 10 at 12:25
  • 1
    $\begingroup$ I would recommend you modify your question to better reflect your requirements. $\endgroup$
    – codeR
    Commented May 10 at 12:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.