1
$\begingroup$

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

$\endgroup$
0
7
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ May 7 '12 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.