Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$? (Set cover).

All upper bounds that I am aware of are

  1. dynamic programming $\mathcal{O}^*(2^n)$
  2. poly-space Measure and Conquer $O(2^{.305(m+n)})$
  3. slightly better $M\&C$ exp-space bound exponential in $m+n$.


  • $\begingroup$ I suggest to add that by "an upper bound that is better than trivial", you mean an algorithm that is exponentially faster than the trivial $O^*(2^m)$ algorithm that goes through all subsets of $\mathcal{S}$. $\endgroup$ – Serge Gaspers Feb 1 '11 at 23:13
  • $\begingroup$ Indeed, I implied that. AW $\endgroup$ – user3599 Feb 4 '11 at 6:53
  • $\begingroup$ You can reduce the general problem to the restricted case that you ask about without increasing $m$ (by much): given any set-cover instance, add 1 set containing $3(m+1)-n$ new elements. So, if you are interested in the hardness of the problem as a function of $m$ only (which seems to be what you are asking about) the restriction $n\ge 3m$ cannot lead to easier instances. (It would seem more plausible that restricting to, say, $n\le 3m$ might make the problem easier. Or maybe I am missing something?) $\endgroup$ – Neal Young Nov 3 '12 at 5:54

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.