セットカバーの問題

集合被覆問題は、組合せ論、コンピュータサイエンス、オペレーションズリサーチ、複雑性理論における古典的な問題です。

集合被覆問題は、要素の集合{1, 2, …, n } (以下、対象とするすべての可能な要素を指定するために宇宙と呼ぶ) と、和が宇宙に等しいm個の部分集合の集合Sが与えられたときに、和が宇宙に等しい Sの最小の部分集合を特定することです。

たとえば、宇宙U = {1, 2, 3, 4, 5}と集合のコレクションS = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} } を考えます。この例では、このコレクションを構成するサブセットが 4 つあるため、 m は4 に等しくなります。 Sの和集合はUに等しくなります。ただし、すべての要素を 2 つのセット{ {1, 2, 3}, {4, 5} } ‍ でカバーできます (図を参照)。ただし、1 つのセットだけではカバーできません。したがって、このUとSの集合カバー問題の解のサイズは 2 です。

より正式には、宇宙との部分集合の族が与えられたとき、集合被覆はの和集合が となる集合のサブ族です。 ${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$${\displaystyle {\mathcal {U}}}$

• 集合被覆決定問題では、入力はペアと整数であり、サイズ以下の集合被覆が存在するかどうかが問題となります。${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$${\displaystyle k}$${\displaystyle k}$
• セットカバー最適化問題では、入力はペアであり、使用するセットが最も少ないセットカバーを見つけることがタスクです。${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$

集合被覆の決定バージョンはNP完全である。これは、1972年にNP完全であると示されたKarpの21のNP完全問題の1つである。集合被覆の最適化/探索バージョンはNP困難である。^{[1]これは、}近似アルゴリズムの「全分野の基礎技術の開発につながった研究」の問題である。^[2]

重み付きセットカバー問題では、各セットに正の重み（コストを表す）が割り当てられ、最小の重みを持つセットカバーを見つけることが目標となります。通常の（重みなしの）セットカバーは、重みが 1 であるすべてのセットに対応します。

分数集合カバー問題 では、集合全体ではなく集合の一部を選択できます。分数集合カバーは、 内の各集合に分数 ([0,1] 内の数値) を割り当て、宇宙の各要素xについて、 x を含む集合の一部の合計が1 以上になるようにします。目標は、分数の合計が可能な限り小さくなる分数集合カバーを見つけることです。(通常の) 集合カバーは、すべての分数が 0 または 1 である分数集合カバーと同等であることに注意してください。したがって、最小の部分カバーのサイズは、最大でも最小カバーのサイズですが、それより小さくなる場合があります。たとえば、宇宙 U = {1, 2, 3}と集合のコレクションS = { {1, 2}, {2, 3}, {3, 1} } を考えます。 最小の集合カバーのサイズは 2 です (例: { {1, 2}, {2, 3} })。しかし、サイズが 1.5 の分数セットカバーがあり、各セットの 0.5 分数が取得されます。${\displaystyle {\mathcal {S}}}$

集合被覆問題は、次のような整数線形計画法（ILP）として定式化できる。^[3]

被覆制約をより簡潔に表現するには、接続行列 を定義します。ここで、各行は要素に対応し、各列はセットに対応します。要素 e がセット s 内にある場合は 、そうでない場合は です。被覆制約は と記述できます。 ${\displaystyle A}$${\displaystyle A_{e,s}=1}$${\displaystyle A_{e,s}=0}$${\displaystyle Ax\geqslant 1}$

重み付きセットカバーは、最小化する目的関数が（セット の重み）であることを除いて、上記のプログラムと同一のプログラムで記述されます。 ${\displaystyle \sum _{s\in {\mathcal {S}}}w_{s}x_{s}}$${\displaystyle w_{s}}$${\displaystyle s\in {\mathcal {S}}}$

分数集合被覆は、が非整数になる可能性があることを除いて、上記のプログラムと同一のプログラムによって記述されます。そのため、最後の制約は に置き換えられます。 ${\displaystyle x_{s}}$${\displaystyle 0\leq x_{s}\leq 1}$

この線形計画法は、目的関数のすべての係数と制約の両辺が非負であるため、被覆問題に対するより一般的なクラスの線形計画法に属します。線形計画法の積分性ギャップは最大で(ここで は宇宙の大きさ) です。この緩和により、最小集合被覆問題に対する因数近似アルゴリズムが得られることが示されています。 ^[4]詳細な説明については、 ランダム化丸め#setcover を参照してください。${\displaystyle \scriptstyle \log n}$${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle \log n}$

集合被覆は、ヒット集合問題と同等です。これは、集合被覆のインスタンスを任意の二部グラフとして見ることができることからわかります。このグラフでは、宇宙は左側の頂点で表され、集合は右側の頂点で表され、辺は集合への要素の所属を表します。この場合の課題は、右側の頂点のそれぞれと非自明な交差を持つ、左側の頂点の最小基数サブセットを見つけることであり、これはまさにヒット集合問題です。

計算幾何学の分野では、幾何学的オブジェクトの集合に対するヒット集合は、スタブ集合またはピアシング集合とも呼ばれる。^[5]

集合被覆の多項式時間近似のための貪欲アルゴリズムがあり、これは 1 つのルールに従って集合を選択する: 各段階で、被覆されていない要素の最大数を含む集合を選択する。この方法は、バケット キューを使用して集合の優先順位付けを行うことで、入力集合のサイズの合計に線形の時間で実装できる。^[6]このアルゴリズムは、被覆する集合のサイズがである場合、近似比 を達成する。 ^[7]つまり、最小の被覆の 倍の大きさになる可能性がある被覆を見つける。ここで、 は-番目の調和数である。 ${\displaystyle H(s)}$${\displaystyle s}$${\displaystyle H(n)}$${\displaystyle H(n)}$${\displaystyle n}$$${\displaystyle H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1}$$

この貪欲アルゴリズムは、実際には の近似比を達成します。ここで はの最大濃度集合です。しかし、密なインスタンスの場合、すべての に対して -近似アルゴリズムが存在します。^[8]${\displaystyle H(s^{\prime })}$${\displaystyle s^{\prime }}$${\displaystyle S}$${\displaystyle \delta -}$${\displaystyle c\ln {m}}$${\displaystyle c>0}$

貪欲アルゴリズムが近似比 を達成する標準的な例があります。宇宙は要素で構成されています。集合システムは、それぞれサイズが である2 つの互いに素な集合 と、各 の要素の半分を含む2 つの追加の互いに素な集合 で構成されています。この入力では、貪欲アルゴリズムは集合 を その順序で取得しますが、最適解は と のみで構成されます。のこのような入力の例を右に示します。 ${\displaystyle \log _{2}(n)/2}$${\displaystyle n=2^{(k+1)}-2}$${\displaystyle k}$${\displaystyle S_{1},\ldots ,S_{k}}$${\displaystyle 2,4,8,\ldots ,2^{k}}$${\displaystyle T_{0},T_{1}}$${\displaystyle S_{i}}$${\displaystyle S_{k},\ldots ,S_{1}}$${\displaystyle T_{0}}$${\displaystyle T_{1}}$${\displaystyle k=3}$

近似不可能性の結果は、貪欲アルゴリズムが、妥当な複雑さの仮定の下で、低次の項までの集合被覆に対する本質的に最良の多項式時間近似アルゴリズムであることを示している（下記の近似不可能性の結果を参照）。貪欲アルゴリズムのより厳密な分析は、近似率が正確に であることを示している。^[9]${\displaystyle \ln {n}-\ln {\ln {n}}+\Theta (1)}$

各要素が最大でf 個の集合に出現する場合、 LP 緩和法を使用して最適値をf倍以内に近似する解を多項式時間で見つけることができます。

上記の整数線形計画において、制約がすべてのSに対して に置き換えられると、(非整数)線形計画Lになります。アルゴリズムは次のように記述できます。 ${\displaystyle x_{S}\in \{0,1\}}$${\displaystyle x_{S}\geq 0}$${\displaystyle {\mathcal {S}}}$

1. 線形計画法を解く多項式時間法を使用して、プログラムLの最適解O を見つけます。
2. 対応する変数xS_が解Oにおいて少なくとも1/ fの値を持つすべての集合Sを選択する。^[10]

が宇宙の大きさを指すとき、Lund & Yannakakis (1994) は、 NP が準多項式時間アルゴリズムを持たない限り、集合被覆を の係数以内に多項式時間で近似することはできないことを示しました。Feige (1998)は、同じ仮定の下でこの下限を に改善しました。これは、本質的に貪欲アルゴリズムによって達成される近似率と一致します。Raz & Safra (1997) は、 P NPという弱い仮定の下で、 （ただし は特定の定数）の下限を確立しました。より高い の値を持つ同様の結果が、最近 Alon、Moshkovitz、Safra (2006) によって証明されました。Dinur & Steurer (2013) は、 P NPでない限りを に近似できないことを証明することで、最適近似不可能性を示しました。 ${\displaystyle n}$${\displaystyle {\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}}$${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle c\cdot \ln {n}}$${\displaystyle c}$${\displaystyle \not =}$${\displaystyle c}$${\displaystyle {\bigl (}1-o(1){\bigr )}\cdot \ln {n}}$${\displaystyle =}$

低頻度システムでは、Dinur ら (2003) は、セットカバーを よりも良く に近似することは NP 困難であることを証明しました。ユニーク ゲーム予想が正しい場合、Khot と Regev (2008) によって証明されたように、これを に改善できます。 ${\displaystyle f-1-\epsilon }$${\displaystyle f-\epsilon }$

Trevisan (2001) は、最大で のセットを持つセットカバーインスタンスは、P NPでない限り、 よりも良い係数に近似できないことを証明しており、この場合、貪欲アルゴリズムの の近似は本質的に厳密になります。 ${\displaystyle \Delta }$${\displaystyle \ln \Delta -O(\ln \ln \Delta )}$${\displaystyle =}$${\displaystyle \ln \Delta +1}$

上で述べた重み付き集合被覆の整数線形計画を緩和すると、ランダム化丸めを使用して係数近似値を得ることができます。重みなし集合被覆は重み付きの場合に適応できます。^[11]${\displaystyle O(\log n)}$

• ヒットセットは、セットカバーと同等の再定式化です。
• 頂点カバーはヒッティング セットの特殊なケースです。
• エッジ カバーは、セット カバーの特殊なケースです。
• 幾何集合被覆は、宇宙が 内の点の集合であり、集合が宇宙と幾何形状 (円盤、長方形など) の交差によって誘導される場合の集合被覆の特殊なケースです。${\displaystyle \mathbb {R} ^{d}}$
• セット梱包
• 最大カバレッジ問題は、できるだけ多くの要素をカバーするために最大 k 個のセットを選択することです。
• 支配集合は、グラフ内の頂点の集合 (支配集合) を選択する問題です。このとき、他のすべての頂点は支配集合内の少なくとも 1 つの頂点に隣接します。支配集合問題は、集合被覆からの還元によって NP 完全であることが示されました。
• 正確な被覆問題とは、複数の被覆集合に含まれる要素がない集合被覆を選択することです。
• 赤青セットの表紙。^[12]
• セットカバー誘拐。
• 単調双対化は、すべての最小ヒットセットをリストするか、与えられたセットファミリーのすべての最小セットカバーをリストすることと同等の計算問題です。^[13]

• Alon, Noga ; Moshkovitz, Dana ; Safra, Shmuel (2006)、「k-制限のための集合のアルゴリズム構築」、ACM Trans. Algorithms、2 (2): 153–177、CiteSeerX  10.1.1.138.8682、doi :10.1145/1150334.1150336、ISSN  1549-6325、S2CID  11922650。
• トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2001)、『アルゴリズム入門』、マサチューセッツ州ケンブリッジ: MIT Press および McGraw-Hill、pp. 1033–1038、ISBN 978-0-262-03293-3
• フェイジ、ウリエル(1998)、「集合被覆を近似するための ln n の閾値」、Journal of the ACM、45 (4): 634–652、CiteSeerX  10.1.1.70.5014、doi :10.1145/285055.285059、ISSN  0004-5411、S2CID  52827488。
• Karpinski, Marek; Zelikovsky, Alexander (1998)、「被覆問題の密なケースの近似」、ネットワーク設計に関する DIMACS ワークショップの議事録: 接続性と施設の場所、第 40 巻、アメリカ数学会、pp. 169–178、ISBN 9780821870846
• ルンド、カーステン;ヤンナカキス、ミハリス(1994)、「近似最小化問題の困難性について」、Journal of the ACM、41 (5): 960–981、doi : 10.1145/185675.306789、ISSN  0004-5411、S2CID  9021065。
• Raz, Ran ; Safra, Shmuel (1997)、「NP のサブ定数エラー確率低次テストとサブ定数エラー確率 PCP 特性」、STOC '97: 第 29 回 ACM コンピューティング理論シンポジウム議事録、ACM、pp. 475–484、ISBN 978-0-89791-888-6。
• Dinur, Irit ; Steurer, David (2013)、「並列反復への分析的アプローチ」、STOC '14: 第 46 回 ACM コンピューティング理論シンポジウム議事録、ACM、pp. 624–633。
• Vazirani、Vijay V. (2001)、近似アルゴリズム(PDF)、Springer-Verlag、ISBN 978-3-540-65367-7
• Corte, ベルンハルト; Vygen、Jens (2012)、Combinatorial Optimization: Theory and Algorithms (5 ed.)、Springer、ISBN 978-3-642-24487-2
• Cardoso, Nuno; Abreu, Rui (2014)、「最小ヒットセットを計算するための効率的な分散アルゴリズム」(PDF)、第 25 回国際診断原理ワークショップの議事録、オーストリア、グラーツ、doi :10.5281/zenodo.10037{{citation}}: CS1 maint: location missing publisher (link)
• ディヌール、イリット、グルスワミ、ベンカテサン、コット、スバッシュ、レゲブ、オデッド（2003）、新しい多層 PCP とハイパーグラフ頂点カバーの難しさ、Association for Computing Machinery、pp. 595–601、doi :10.1145/780542.780629、ISBN 1581136749
• Khot, Subhash ; Regev, Oded (2008)、頂点被覆を 2− ϵ {\displaystyle \epsilon } 以内に近似することは難しいかもしれない、Journal of Computer and System Sciences、pp. 335–349、doi :10.1016/j.jcss.2007.06.019
• トレヴィサン、ルカ(2001)、「制限された次数インスタンスの最適化問題に対する近似不可能性の結果」、第 33 回 ACM コンピューティング理論シンポジウム議事録、Association for Computing Machinery、pp. 453–461、doi :10.1145/380752.380839、ISBN 1-58113-349-9

ウィキメディア・コモンズには、集合被覆問題に関連するメディアがあります。

• セットカバー、セットパッキング、勝者決定のための最適解を隠したベンチマーク
• NP 最適化問題の概要 - 最小集合カバー