セットカバーの問題

集合被覆問題は、組み合わせ論、コンピュータ科学、オペレーションズリサーチ、および計算複雑性理論における古典的な問題である。

要素の集合{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] の数値）を割り当てることです。$\displaystyle {\mathcal {S}}}$宇宙の各要素xに対して、 x を含む集合の割合の合計が 1 以上となるような集合被覆を定義とする。目標は、割合の合計が可能な限り小さくなるような分数集合被覆を見つけることである。通常の集合被覆は、すべての割合が 0 または 1 である分数集合被覆と同等であることに注意する。したがって、最小の分数被覆のサイズは、最小の被覆のサイズ以上であるが、それより小さくなる場合もある。例えば、宇宙U = {1, 2, 3}と集合の集合S = { {1, 2}, {2, 3}, {3, 1} } を考える。 最小の集合被覆のサイズは 2 であり、例えば{ {1, 2}, {2, 3} } である。しかし、各集合の 0.5 の割合を取ることで、サイズ 1.5 の分数集合被覆が存在する。

容量制約付き集合被覆問題では、各集合は$\displaystyle s\in \mathcal S}$容量に関連付けられています${\displaystyle c_{S}}$これは、カバレッジを提供できる要素の数を表します。目標は、各要素が必要なカバレッジを受けられるように、最適なセットの選択方法を決定することです。

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

被覆制約をより簡潔に表現するために、接続行列を定義することができる。${\displaystyle A}$ここで、各行は要素に対応し、各列は集合に対応し、${\displaystyle A_{e,s}=1}$要素 e が集合 s に含まれる場合、${\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}$。

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

集合被覆問題はヒットセット問題と同等である。部分集合${\displaystyle H}$の${\displaystyle U}$打撃セットと呼ばれるのは、${\displaystyle H\cap S_{j}\neq \emptyset }$すべての人々のために${\displaystyle 1\leq j\leq m}$（つまり、${\displaystyle H}$すべてのサブセットと交差または「ヒット」する${\displaystyle S}$ヒットセット問題とは、最小ヒットセットを見つけることである。${\displaystyle H}$特定の${\displaystyle U}$そして${\displaystyle S}$。

問題が同等であることを示すために、宇宙では${\displaystyle U}$サイズの${\displaystyle n}$およびセットのコレクション${\displaystyle S}$サイズの${\displaystyle m}$構築する${\displaystyle U'=\{1,2,\ldots ,m\}}$そして ${\displaystyle S'_{i}=\{j\mid i\in S_{j}\}}$.それからセットカバー${\displaystyle C}$の${\displaystyle S}$打撃セットに相当する${\displaystyle H'}$の${\displaystyle U'}$どこ${\displaystyle S_{j}\in C\iff j\in H'}$そしてその逆もまた然り。

この等価性は、問題を二部グラフとして表現することによっても視覚化できます。${\displaystyle n+m}$頂点、${\displaystyle n}$左側の頂点は、${\displaystyle U}$、 そして${\displaystyle m}$右側の頂点は、${\displaystyle S}$、および集合メンバーシップを表すエッジ（つまり、${\displaystyle i}$左側の 番目の頂点と${\displaystyle j}$右側の番目の頂点である場合。${\displaystyle i\in S_{j}}$)すると、集合被覆は部分集合になります。${\displaystyle C}$右頂点の 1 つで、各左頂点が少なくとも 1 つのメンバーに隣接している${\displaystyle C}$打撃セットは部分集合である${\displaystyle H}$左頂点の 1 つで、各右頂点が少なくとも 1 つのメンバーに隣接している${\displaystyle H}$これらの定義は、左右が入れ替わっている点を除いて全く同じです。しかし、二部グラフの側面には特別なことは何もありません。要素を配置することもできました。${\displaystyle U}$右側には、 ${\displaystyle S}$左側には、上記のグラフの鏡像となるグラフが作成されます。これは、元のグラフにおけるセットカバーが、鏡像グラフにおけるセットヒットと等価であり、その逆もまた同様であることを示しています。

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

集合被覆の多項式時間近似のための貪欲アルゴリズムがあり、各段階で未被覆要素が最も多い集合を選択するというルールに従って集合を選択します。この方法は、バケットキューを使用して集合の優先順位付けを行うことで、入力集合のサイズの合計に対して線形の時間で実装できます。^{[ 6 ]}近似比は${\displaystyle H(s)}$、 どこ${\displaystyle s}$は、カバーする集合のサイズです。^{[ 7 ] [ 8 ] [ 9 ]} 言い換えれば、カバーを見つけると、${\displaystyle H(n)}$最小値の倍の大きさで、${\displaystyle H(n)}$は${\displaystyle n}$第 1 次高調波番号: $${\displaystyle H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1}$$

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

貪欲アルゴリズムが近似比を達成する標準的な例がある。${\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}}$それぞれ、さらに互いに素な2つの集合${\displaystyle T_{0},T_{1}}$それぞれが各要素の半分を含んでいる${\displaystyle S_{i}}$この入力に対して、貪欲アルゴリズムはセットを取得します。 ${\displaystyle S_{k},\ldots ,S_{1}}$、その順序で、最適解は${\displaystyle T_{0}}$そして${\displaystyle T_{1}}$。そのような入力の例は、${\displaystyle k=3}$右側に写っているのがそれです。

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

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

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

1. 線形計画問題を解くための多項式時間法を用いて、プログラムLの最適解Oを求めよ。
2. 対応する変数x _{S の}値が解Oにおいて少なくとも 1/ fであるようなすべての集合Sを選択する。^{[ 12 ]}

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

低周波システムでは、Dinur ら (2003) は、集合被覆を よりも高い精度で近似することは NP 困難であることを証明しました。${\displaystyle f-1-\epsilon }$ユニークゲーム予想が正しい場合、これは次のように改善できます。${\displaystyle f-\epsilon }$Khot & Regev (2008)によって証明されています。

Trevisan (2001) は、最大でサイズの集合を持つインスタンスを集合で覆うことを証明しています。${\displaystyle \Delta }$より優れた係数で近似することはできません${\displaystyle \ln \Delta -O(\ln \ln \Delta )}$Pでない限り${\displaystyle =}$NPの近似値${\displaystyle \ln \Delta +1}$この場合、貪欲アルゴリズムは本質的にタイトである。

重み付き集合被覆問題^{[ 7 ]}に対する貪欲アルゴリズムは、重みなしバージョンを直接一般化したものである。${\displaystyle {\mathcal {U}}}$そして家族$\displaystyle {\mathcal {S}}}$サブセットの${\displaystyle {\mathcal {U}}}$各セット${\displaystyle S\in {\mathcal {S}}}$非負の重み（コスト）が割り当てられると、アルゴリズムはまだカバーされていない要素のサブセットを維持します。最初は、すべての要素が${\displaystyle {\mathcal {U}}}$が明らかになる。各反復で、アルゴリズムはセットを選択する。${\displaystyle S\in {\mathcal {S}}}$これは、その重量と現在カバーされていない要素の数の比率を最小化します。選択されたセットがソリューションに追加され、その中に含まれるすべての要素がカバー済みとしてマークされます。このプロセスは、すべての要素がカバーされるまで繰り返されます。${\displaystyle {\mathcal {U}}}$がカバーされています。貪欲アルゴリズムは、総重量が最大で の係数である解を生成することが知られています。${\displaystyle H(n)}$最適解の倍数で​​、${\displaystyle H(n)}$は${\displaystyle n}$第 1 次高調波数と${\displaystyle n=|{\mathcal {U}}|}$。

低周波システムでは、すべての要素が最大で${\displaystyle f}$セットでは、決定論的LP丸めアルゴリズムは${\displaystyle f}$-近似。^{[ 13 ]}これは、上記の 問題の線形計画緩和の最適解から始まります。小数値がを超える集合${\displaystyle 1/f}$整数解を形成するように選択される。

集合被覆問題に対する主双対アルゴリズムは、主問題と双対問題の両方の線形計画問題の実行可能解を同時に構築する反復法です。すべての双対変数をゼロに設定して開始し、アルゴリズムは、未被覆要素に対応する双対変数を均一に繰り返し増加させ、ある集合の双対制約がタイトになるまで続けます（つまり、集合内の要素の双対変数の合計がそのコストに等しくなります）。このタイトな集合は主問題の解に追加され、対応する要素を被覆します。すべての要素が被覆されるまでこのプロセスが続きます。このアルゴリズムは、近似比を保証します。${\displaystyle f}$、 どこ${\displaystyle f}$は、任意の要素が属する集合の最大数です。^{[ 14 ]}

ランダム化丸めは、線形計画緩和の解を用いる重み付き集合被覆問題の近似手法である。${\displaystyle {x_{S}^{*}}}$LP緩和問題の最適な分数解となる。各セット${\displaystyle S\in {\mathcal {S}}}$カバーに独立して含まれる可能性が高い${\displaystyle x_{S}^{*}}$期待値の線形性により、選択された集合の期待コストは LP 最適値に等しくなります。要素がカバーされない確率は、確率をスケーリングするか、丸めを繰り返すことで任意に小さくすることができます。標準的な集中境界を使用すると、期待コストが の範囲内にある実行可能な集合カバーが生成されます。${\displaystyle O(\log n)}$最適解の係数、ここで${\displaystyle n}$宇宙の大きさに匹敵する。

^{参考文献は[ 15 ]}および^{[ 16 ]}に記載されています。

• ヒッティングセットは、セットカバーの言い換えと同等である。
• 頂点カバーは、ヒッティングセットの特殊なケースです。
• エッジカバーはセットカバーの特殊なケースです。
• 幾何学的集合被覆は、宇宙が点の集合である場合の集合被覆の特殊なケースです。$\displaystyle \mathbb {R} ^{d}}$そして、これらの集合は、宇宙と幾何学的形状（例えば、円盤、長方形）の交わりによって誘導される。
• 集合パッキングとは、互いに素な集合を最大数選択する問題のことである。
• 最大被覆問題とは、最大で${\displaystyle k}$できるだけ多くの要素を網羅するように設定されています。
• 支配集合問題とは、グラフにおいて、他のすべての頂点が支配集合内の少なくとも1つの頂点に隣接するような頂点の集合（支配集合）を選択する問題である。支配集合問題は、集合被覆問題からの帰着によってNP完全であることが示された。
• 厳密な被覆問題とは、どの要素も複数の被覆集合に含まれないような被覆集合を選択することである。
• 赤青集合被覆は集合被覆の一般化であり、宇宙の要素は赤または青のいずれかに色分けされ、与えられた集合のサブコレクションを選択して、すべての青い要素をカバーしつつ、赤い要素のカバー数を最小限に抑えることが目標です。^{[ 17 ]}
• 集合被覆アブダクションは、一連の観測値と一連の仮説が与えられたときに、すべての観測値の効果を含むような仮説のサブセットを選択することを目的とする関連問題である。
• 単調双対化は、与えられた集合族のすべての最小ヒット集合を列挙するか、すべての最小集合被覆を列挙することと同等の計算問題である。^{[ 18 ]}

• 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
• Feige, Uriel (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巻、アメリカ数学会、 169–178 ページ、ISBN  9780821870846
• Lund, Carsten ; Yannakakis, Mihalis (1994)、「最小化問題の近似の難しさについて」、Journal of the ACM、41 (5): 960–981、doi : 10.1145/185675.306789、ISSN 0004-5411、S2CID 9021065  。
• Raz, Ran ; Safra, Shmuel (1997)、「準定数エラー確率低次数テストと準定数エラー確率PCPによるNPの特性評価」、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メンテナンス: 場所の発行元が見つかりません (リンク)
• Dinur, Irit ; Guruswami, Venkatesan ; Khot, Subhash ; Regev, Oded (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 
• Trevisan, Luca (2001)、「次数が制限されたインスタンス上の最適化問題に対する非近似可能性の結果」、第33回ACM理論計算シンポジウム議事録、Association for Computing Machinery、pp. 453–461、doi : 10.1145/380752.380839、ISBN  1-58113-349-9

• セットカバレッジ、セットパッキング、勝者決定のための隠れた最適解を含むベンチマーク（ 2017年7月25日にWayback Machineにアーカイブ済み）
• NP最適化問題集 - 最小集合被覆