<p>Suppose $U = \{1, 2, \cdots, n\}$ is a universe and $\mathcal S = \{S_1, S_2, \cdots, S_m\}$ is a collection of sets such that each set contains exactly $c$ elements, where $c$ is a constant.</p>

<p>In this case, a $c$-approximation is easy. It is also possible to improve that to <a href="http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf" rel="nofollow">$\ln c + 1$-approximation</a>. </p>

<p>My question is following:
<br>Suppose along with this special set cover instance, you are told that an exact cover (of size $n/c$) exists. Is it possible to get a better approximation factor? What is known about hardness of approximation in this case?</p>

CC BY-SA 3.0
2016-08-25T23:41:46.673Z
Have you looked at the standard hardness-of-approximation results in the literature for set cover, to see if any of their constructions/proofs can be carried over to this setting?  Can you summarize them and what the barrier seems to be for each, if any?
D.W.
CC BY-SA 3.0
2016-08-26T21:49:46.927Z
In particular, the construction in Feige's paper seems to have your two properties: all sets have the same number of elements, and in the YES case the cover is exact. Perhaps the construction in Moshkovitz's paper has the same properties. If you had an algorithm with a better approximation ratio on these YES instances, you will be able to tell them apart from NO instances.
Yuval Filmus
<set-cover><exact-cover>
Approximating set cover when it is known that an exact set cover exists
taninamdar
# Approximating set cover when it is known that an exact set cover exists

(Asked by: username_0 on 2016-08-24)

Suppose $U = \{1, 2, \cdots, n\}$ is a universe and $\mathcal S = \{S\_1, S\_2, \cdots, S\_m\}$ is a collection of sets such that each set contains exactly $c$ elements, where $c$ is a constant.

In this case, a $c$-approximation is easy. It is also possible to improve that to [$\ln c + 1$-approximation](http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/lecture03.pdf).

My question is following:
  
Suppose along with this special set cover instance, you are told that an exact cover (of size $n/c$) exists. Is it possible to get a better approximation factor? What is known about hardness of approximation in this case?

**Tags:** set-cover, exact-cover

> **Comments:**
> **username_1**: Have you looked at the standard hardness-of-approximation results in the literature for set cover, to see if any of their constructions/proofs can be carried over to this setting?  Can you summarize them and what the barrier seems to be for each, if any?  
> **username_2**: In particular, the construction in Feige's paper seems to have your two properties: all sets have the same number of elements, and in the YES case the cover is exact. Perhaps the construction in Moshkovitz's paper has the same properties. If you had an algorithm with a better approximation ratio on these YES instances, you will be able to tell them apart from NO instances.  

---

## 0 answers

