# Worst-case asymptotic-complexity of the Set-cover problem?

What's the worst-case asymptotic-complexity of the Set-cover problem in 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

There is a simple greedy polynomial time approximation 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.
• 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. May 7 '12 at 17:58