# Integrality gap of Maximum Coverage LP

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$$?

• What do you mean by $LP(I) = 1$? Commented May 10 at 7:24
• 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}$. Commented May 10 at 7:27
• 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? Commented May 10 at 7:29
• Yes, I want to find a counterexample. Commented May 10 at 12:25
• I would recommend you modify your question to better reflect your requirements. Commented May 10 at 12:33