<p>I'm considering the <strong>minimum set cover</strong> problem with the constraint that each set contains at most <span class="math-container">$k$</span> elements.
Here, <span class="math-container">$k$</span> depends on the size of the universe. </p>

<p>For example, <span class="math-container">$k$</span> may equal <span class="math-container">$\log n,\sqrt n$</span>, etc., if the universe is <span class="math-container">$\{1,2,\ldots,n\}$</span>.</p>

<p>In <a href="https://cstheory.stackexchange.com/questions/191/bounded-cardinality-bounded-frequency-set-cover-hardness-of-approximation">this post</a> and <a href="https://dl.acm.org/citation.cfm?doid=380752.380839" rel="nofollow noreferrer">this paper of Luca Trevisan</a>, they seem to deal with constant <span class="math-container">$k$</span>. In <a href="https://dl.acm.org/citation.cfm?doid=285055.285059" rel="nofollow noreferrer">this paper of Uriel Feige</a>, there is no size bound.</p>

<p>Though I suspect it is still <span class="math-container">$(1-o(1))\ln k$</span> inapproximable, any reference on this would be nice.</p>

CC BY-SA 4.0
2019-06-05T21:38:56.187Z
I seem to remember your guess is correct but don’t remember citations off the top of my head...
daniello
CC BY-SA 4.0
2019-06-06T15:56:01.567Z
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
CC BY-SA 4.0
2019-06-06T16:07:58.750Z
@daniello thanks!
Shlw Kevin
CC BY-SA 4.0
2019-06-06T16:14:29.507Z
@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
<reference-request><approximation-hardness><set-cover>
Hardness of Approximation of Set Cover with Growing Size Bound
Shlw Kevin
# Hardness of Approximation of Set Cover with Growing Size Bound

(Asked by: username_0 on 2019-06-05)

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](https://cstheory.stackexchange.com/questions/191/bounded-cardinality-bounded-frequency-set-cover-hardness-of-approximation) and [this paper of Luca Trevisan](https://dl.acm.org/citation.cfm?doid=380752.380839), they seem to deal with constant $k$. In [this paper of Uriel Feige](https://dl.acm.org/citation.cfm?doid=285055.285059), there is no size bound.

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

**Tags:** reference-request, approximation-hardness, set-cover

> **Comments:**
> **username_1**: I seem to remember your guess is correct but don’t remember citations off the top of my head...  
> **username_2**: 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  
> **username_0**: @username_1 thanks!  
> **username_0**: @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.  

---

## 0 answers

