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.

  • $\begingroup$ I seem to remember your guess is correct but don’t remember citations off the top of my head... $\endgroup$
    – daniello
    Commented Jun 5, 2019 at 21:38
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Jun 6, 2019 at 15:56
  • $\begingroup$ @daniello thanks! $\endgroup$
    – Shlw Kevin
    Commented Jun 6, 2019 at 16:07
  • $\begingroup$ @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. $\endgroup$
    – Shlw Kevin
    Commented Jun 6, 2019 at 16:14


Your Answer

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