我最近在研究一个我认为是布景封面问题的分支问题。但是，我的问题中的集合数有 2^n 之多。而我发现的近似算法似乎只有在集合不多的情况下才有效。我想知道是否存在适合 2^n 集合的算法？
谢谢您的回答!!!
最佳答案
不，没有比对数更好的近似值了。见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.
关于algorithm - 当集合太多时，比如 2^n 集合，集合覆盖中是否有任何近似算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11115240/