3

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.

Shlw Kevin
  • 101
  • 2
  • I seem to remember your guess is correct but don’t remember citations off the top of my head... – daniello Jun 05 '19 at 21:38
  • 1
    This note by Jelani Nelso is not exactly what you are looking for but still be useful. https://eccc.weizmann.ac.il//eccc-reports/2007/TR07-105/revisn01.pdf – Chandra Chekuri Jun 06 '19 at 15:56
  • @daniello thanks! – Shlw Kevin Jun 06 '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 06 '19 at 16:14

0 Answers0