<p>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$?
(<a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">Set cover</a>).</p>

<p>All upper bounds that I am aware of are </p>

<ol>
<li> dynamic programming $\mathcal{O}^*(2^n)$</li>
<li> poly-space Measure and Conquer $O(2^{.305(m+n)})$</li>
<li> slightly better $M\&amp;C$ exp-space bound exponential in $m+n$.</li>
</ol> 

<p>Thanks.
<br>AW</p>

CC BY-SA 3.0
2012-11-03T05:54:46.263Z
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
CC BY-SA 2.5
2011-02-01T23:13:52.340Z
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
CC BY-SA 2.5
2011-02-04T06:53:08.357Z
Indeed, I implied that. AW
user3599
<ds.algorithms><set-cover><upper-bounds><exp-time-algorithms>
Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$
user3599
# Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$

(Asked by: username_0 on 2011-02-01)

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](http://en.wikipedia.org/wiki/Set_cover_problem)).

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

**Tags:** ds.algorithms, set-cover, upper-bounds, exp-time-algorithms

> **Comments:**
> **username_2**: 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}$.  
> **username_0**: Indeed, I implied that. AW  
> **username_1**: 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?)  

---

## 0 answers

