2

I am recently working on a problem which I think is a fork of the set cover problem. However, the number of sets in my problem is as large as 2^n. And the approximate alogrithms I've found seem to be only effective when there are not too many sets. I wonder there exists an alogorithm that suits with 2^n sets?

Thank you for your answering!!!

Yihong Xiang
  • 75
  • 5

1 Answers1

0

No there isn't better approximation than logarithmic one. see wiki:

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover, under plausible complexity assumptions. Lund & Yannakakis (1994) showed that set covering cannot be approximated in polynomial time to within a factor of 0.72 ln(n), unless NP has quasi-polynomial time algorithms.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • I know the approximate ratio can not be less than ln(n). I am tring to figure out if there are algorithms that can deal with large number of sets (as large as 2^n) in set cover problem. – Yihong Xiang Jun 20 '12 at 08:36
  • 1
    Your input is too big, You could use greedy approach and if your original set is of size `n`, soon you will find a cover in most cases, but you couldn't expect good result in worse case, because at least you should iterate inputs once, which takes too many time, but may be if you say your original problem (IMO in new thread) it would be better, may be we could suggest some other ways. – Saeed Amiri Jun 20 '12 at 08:40
  • Since the n in my problem can be as large as 100 and even bigger, I must abandon the iteration way. I want to write a algorithm whose complexity is polynomial and the approximate ratio can reach ln(n), at least the lower bound. Am I too gready??? – Yihong Xiang Jun 20 '12 at 09:01
  • 2
    轩辕魂: if n > 100, then 2^n > 1267650600228229401496703205376, you will not handle data of that size. – sdcvvc Jun 21 '12 at 04:15