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
Worst-case asymptotic-complexity of the Set-cover problem?
cc.complexity theory;time complexity;set cover;notation
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.