我最近正在研究一个我认为是集合封面问题的分支的问题。但是，我的问题中的集合数高达 2^n。而且我发现的近似算法似乎只有在没有太多集合的情况下才有效。我想知道是否存在适合 2^n 组的算法？
谢谢你的回答！！！
问问题
148 次
不，没有比对数更好的近似值了。见维基：
不可近似性结果表明，在合理的复杂性假设下，贪心算法本质上是集合覆盖的最佳可能多项式时间逼近算法。Lund & Yannakakis (1994) 表明集合覆盖不能在多项式时间内逼近到 0.72 ln(n) 的因子内，除非 NP 具有准多项式时间算法。