私は最近、セット カバーの問題のフォークと思われる問題に取り組んでいます。ただし、私の問題のセット数は 2^n にもなります。そして、私が見つけたおおよそのアルゴリズムは、セットがあまり多くない場合にのみ効果があるようです. 2^n集合に合うアルゴリズムってあるのかな？
ご回答ありがとうございます!!!
いいえ、対数よりも優れた近似はありません。ウィキを参照してください:
非近似性の結果は、もっともらしい複雑さの仮定の下で、貪欲なアルゴリズムがセット カバーのための可能な限り最良の多項式時間近似アルゴリズムであることを示しています。Lund & Yannakakis (1994) は、NP に準多項式時間アルゴリズムがない限り、セット カバーリングを多項式時間で 0.72 ln(n) の係数内に近似できないことを示しました。