<p>I don't see how you can say that SCP or any other problem has "worst-case asymptotic complexity", but surely an algorithm solving it can have. However, the problem is NP-complete, and the optimization version is NP-hard. </p>

<p>For an exact algorithm, this is clearly a "theoretical limit". For an exact algorithm, see for example E. Balas and M. C. Carrera, A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering, Operations Research 44, 875-890, 1996. According to <a href="http://www.dei.unipd.it/~fisch/papers/survey_set_covering_problem.pdf">A. Caprara et al., Algorithms for the Set Covering Problem, 2000</a>, this algorithm of Balas and Carrera is the fastest known exact algorithm. The result is a bit old already, so I'm not sure if there are newer and faster exact algorithms.</p>

<p>There is a <a href="http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm">simple greedy polynomial time approximation algorithm</a> with an approximation ratio of $H_n$, where $H_n$ is the $n$th harmonic number. Under reasonable assumptions, this is the best one can do, since if there exists a $c \ln n$-approximation algorithm for the (unweighted) set cover problem for some constant $c &lt; 1$, then there is an $O(n^{O(\log \log n)})$-time deterministic algorithm for each NP-complete problem. I think the Wikipedia page gives the essential references.</p>

CC BY-SA 3.0
2012-05-07T17:58:20.950Z
Actually Feige shows if it's possible to approximate Set Cover better than $(1-o(1))\ln n$ then there is an $n^{O(\log\log n)}$ algorithm for NP. Other people have subsequently shown (as byproducts of improved PCPs) that  for some $c > 0$, no $c\ln n$ approximation is possible unless P=NP.
Yuval Filmus
CC BY-SA 3.0
2012-05-07T10:25:00.190Z
2012-05-07T12:03:59.683Z
2012-05-07T12:03:59.683Z
Juho
<p><strong>What's the worst-case asymptotic-complexity of the <a href="http://en.wikipedia.org/wiki/Set_cover_problem" rel="nofollow">Set-cover problem</a> in <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow">Big O notation</a>?</strong></p>

<p>I've been developing some novel techniques to try and solve this problem but am having trouble finding the theoretical limits I need to surpass.</p>

<p>Thanks for all information</p>

<cc.complexity-theory><time-complexity><set-cover><notation>
Worst-case asymptotic-complexity of the Set-cover problem?
A T
# Worst-case asymptotic-complexity of the Set-cover problem?

(Asked by: username_0 on 2012-05-07)

**What's the worst-case asymptotic-complexity of the [Set-cover problem](http://en.wikipedia.org/wiki/Set_cover_problem) in [Big O notation](http://en.wikipedia.org/wiki/Big_O_notation)?**

I've been developing some novel techniques to try and solve this problem but am having trouble finding the theoretical limits I need to surpass.

Thanks for all information

**Tags:** cc.complexity-theory, time-complexity, set-cover, notation


---

## 1 answers

### Answer by username_1 on 2012-05-07. Score: 7 | Accepted answer

I don't see how you can say that SCP or any other problem has "worst-case asymptotic complexity", but surely an algorithm solving it can have. However, the problem is NP-complete, and the optimization version is NP-hard.

For an exact algorithm, this is clearly a "theoretical limit". For an exact algorithm, see for example E. Balas and M. C. Carrera, A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering, Operations Research 44, 875-890, 1996. According to [A. Caprara et al., Algorithms for the Set Covering Problem, 2000](http://www.dei.unipd.it/~fisch/papers/survey_set_covering_problem.pdf), this algorithm of Balas and Carrera is the fastest known exact algorithm. The result is a bit old already, so I'm not sure if there are newer and faster exact algorithms.

There is a [simple greedy polynomial time approximation algorithm](http://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm) with an approximation ratio of $H\_n$, where $H\_n$ is the $n$th harmonic number. Under reasonable assumptions, this is the best one can do, since if there exists a $c \ln n$-approximation algorithm for the (unweighted) set cover problem for some constant $c < 1$, then there is an $O(n^{O(\log \log n)})$-time deterministic algorithm for each NP-complete problem. I think the Wikipedia page gives the essential references.

> **Comments:**
> **username_2**: Actually Feige shows if it's possible to approximate Set Cover better than $(1-o(1))\ln n$ then there is an $n^{O(\log\log n)}$ algorithm for NP. Other people have subsequently shown (as byproducts of improved PCPs) that  for some $c > 0$, no $c\ln n$ approximation is possible unless P=NP.  

---

