# Hardness of Approximation of Set Cover with Growing Size Bound

I'm considering the minimum set cover problem with the constraint that each set contains at most $$k$$ elements. Here, $$k$$ depends on the size of the universe.

For example, $$k$$ may equal $$\log n,\sqrt n$$, etc., if the universe is $$\{1,2,\ldots,n\}$$.

In this post and this paper of Luca Trevisan, they seem to deal with constant $$k$$. In this paper of Uriel Feige, there is no size bound.

Though I suspect it is still $$(1-o(1))\ln k$$ inapproximable, any reference on this would be nice.

• I seem to remember your guess is correct but don’t remember citations off the top of my head... – daniello Jun 5 '19 at 21:38
• This note by Jelani Nelso is not exactly what you are looking for but still be useful. eccc.weizmann.ac.il//eccc-reports/2007/TR07-105/revisn01.pdf – Chandra Chekuri Jun 6 '19 at 15:56
• @daniello thanks! – Shlw Kevin Jun 6 '19 at 16:07
• @ChandraChekuri thanks! Actually I skimmed this before. If I understand correctly, the parameter in it is the number of sets. Then I don’t quite see clear connection here. – Shlw Kevin Jun 6 '19 at 16:14