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 Jun 5 '19 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$ – Chandra Chekuri Jun 6 '19 at 15:56
  • $\begingroup$ @daniello thanks! $\endgroup$ – Shlw Kevin Jun 6 '19 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 Jun 6 '19 at 16:14

Your Answer

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

Browse other questions tagged or ask your own question.