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.

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?

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Aug 25, 2016 at 23:41
  • $\begingroup$ 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. $\endgroup$ Commented Aug 26, 2016 at 21:49


Your Answer

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

Browse other questions tagged or ask your own question.