當集合數量太多，例如2^n集合時，集合覆蓋中是否有任何appproximate算法？

我最近正在研究一個我認爲是集合覆蓋問題的分支的問題。但是，我的問題集的數量大到2^n。我發現的近似算法似乎只在沒有太多組時纔有效。我想知道存在一個適合2^n集合的算法嗎？當集合數量太多，例如2^n集合時，集合覆蓋中是否有任何appproximate算法？

謝謝您的回答！

不，沒有比對數更接近的近似值。看到wiki：

Inapproximability結果表明，該貪婪算法是基本上是機殼的最可能的多項式時間近似算法，根據可信的複雜性假設。隆德& Yannakakis（1994）表明，覆蓋集不能近似在多項式時間來 0.72 LN（n）的係數內，除非NP具有準多項式時間算法。

2012-06-20 08:24:13

我知道近似比例不能小於ln（n）。我試圖弄清楚在集合覆蓋問題中是否有能夠處理大量集合（大至2^n）的算法。 –

您的輸入太大，您可以使用貪婪的方法，如果您的原始大小爲'n'，很快您會在大多數情況下找到封面，但您不能期望在更糟糕的情況下獲得好結果，因爲至少您應該迭代一次輸入，這需要太多時間，但可能是如果你說你原來的問題（國際海事組織在新的線程），它會更好，也許我們可以建議一些其他方式。 –

由於我的問題中的n可能大到100甚至更大，我必須放棄迭代方式。我想寫一個算法，其複雜度是多項式的，近似比率可以達到ln（n），至少是下限。我是否已經準備好了？ –

回答