# Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$

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$.

Thanks.
AW

• 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}$. – Serge Gaspers Feb 1 '11 at 23:13
• Indeed, I implied that. AW – user3599 Feb 4 '11 at 6:53
• 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?) – Neal Young Nov 3 '12 at 5:54