最大カバレッジの問題

最大被覆問題は、コンピュータサイエンス、計算複雑性理論、オペレーションズリサーチにおける古典的な問題であり、近似アルゴリズムで広く教えられている問題です。

入力として、いくつかのセットと数値が与えられます。セットには共通の要素が含まれている場合があります。最大数の要素がカバーされるように、つまり、選択したセットの和集合が最大サイズになるように、これらのセットを 最大で選択する必要があります。${\displaystyle k}$${\displaystyle k}$

正式には、（重み付けされていない）最大カバレッジ

インスタンス: 数値とセットのコレクション。${\displaystyle k}$${\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}$

目的:カバーされる要素の数が最大になるような集合のサブセットを見つけます。${\displaystyle S'\subseteq S}$${\displaystyle \left|S'\right|\leq k}$${\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}$

最大被覆問題はNP困難であり、標準的な仮定の下では の範囲内で近似できる。この結果は本質的に、基数制約を持つサブモジュラ関数の最大化に使用される汎用貪欲アルゴリズムによって達成される近似率と一致する 。^[1]${\displaystyle 1-{\frac {1}{e}}+o(1)\approx 0.632}$

最大被覆問題は、次の整数線形計画法として定式化できます。

最大被覆率を求める貪欲アルゴリズムは、1 つのルールに従って集合を選択します。各段階で、未被覆要素の数が最も多い集合を選択します。このアルゴリズムは近似比 を達成することが示されています。^[2] ln 近似可能性の結果は、 でない限り、貪欲アルゴリズムが本質的に最大被覆率を求める最良の多項式時間近似アルゴリズムであることを示しています。^[3]${\displaystyle 1-{\frac {1}{e}}}$${\displaystyle P=NP}$

近似不可能性の結果は、最大被覆問題を特別なケースとして扱うため、最大被覆問題のすべての拡張に適用されます。

最大被覆問題は道路交通状況に適用できます。一例としては、限られた数のセンサーしか利用できない場合に、公共交通機関ネットワークのどのバス路線に道路の穴検出器を設置して被覆率を最大化するかを選択することが挙げられます。この問題は最大被覆問題の既知の拡張であり、文献ではジュナード・アリとウラジミール・ディオによって初めて研究されました。^[4]

重み付きバージョンでは、すべての要素に重み があります 。タスクは、最大の重みを持つ最大カバレッジを見つけることです。基本バージョンは、すべての重みが である特殊なケースです。 ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle 1}$

最大化します。(カバーされた要素の加重合計を最大化します)。${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

;の対象となります(選択できるセットは 個までです)。 ${\displaystyle \sum {x_{i}}\leq k}$${\displaystyle k}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$; (少なくとも 1 つのセットが選択されている場合)。${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$; (その後がカバーされている場合)${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(表紙に選択された場合) 。${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

各段階での重み付き最大カバレッジを求める貪欲アルゴリズムは、カバーされていない要素の最大重みを含むセットを選択します。このアルゴリズムは近似比を達成します。^[1]${\displaystyle 1-{\frac {1}{e}}}$

予算による最大カバー バージョンでは、すべての要素に重み があるだけでなく、すべてのセットにコスト もあります。 代わりに、カバー内のセット数を制限する予算が与えられます。 この予算によって、選択できるカバーの合計コストが制限されます。 ${\displaystyle e_{j}}$${\displaystyle w(e_{j})}$${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle k}$${\displaystyle B}$${\displaystyle B}$

最大化します。(カバーされた要素の加重合計を最大化します)。${\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}$

が適用されます(選択したセットのコストは を超えることはできません)。 ${\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}}$; (少なくとも 1 つのセットが選択されている場合)。${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{j}\in \{0,1\}}$; (その後がカバーされている場合)${\displaystyle y_{j}=1}$${\displaystyle e_{j}}$

${\displaystyle x_{i}\in \{0,1\}}$(表紙に選択された場合) 。${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

貪欲アルゴリズムは、もはやパフォーマンス保証付きの解を生成しません。つまり、このアルゴリズムの最悪の場合の動作は、最適解から非常に遠い可能性があります。近似アルゴリズムは、次の方法で拡張されます。まず、コストに対する重み付けされた未カバー要素の比率が最良であるセットを選択する修正貪欲アルゴリズムを定義します。次に、濃度 のカバーの中で、予算に違反しない最良カバーを見つけます。このカバーを と呼びます。3番目に、予算に違反しない濃度 のすべてのカバーを見つけます。これらの濃度 のカバーを開始点として使用し、これまでに見つかった最良カバーを維持しながら、修正貪欲アルゴリズムを適用します。このカバーを と呼びます。プロセスの最後に、近似的な最良カバーはまたは になります。このアルゴリズムは、の値に対しての近似比を実現します。 でない限り、これが可能な限り最高の近似比です。^[5]${\displaystyle S_{i}}$${\displaystyle 1,2,...,k-1}$${\displaystyle H_{1}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle H_{2}}$${\displaystyle H_{1}}$${\displaystyle H_{2}}$${\displaystyle 1-{1 \over e}}$${\displaystyle k\geq 3}$${\displaystyle NP\subseteq DTIME(n^{O(\log \log n)})}$

一般化された最大被覆バージョンでは、すべてのセットにはコスト があり、要素の重みとコストは、どのセットがそれをカバーしているかによって異なります。つまり、がセット によってカバーされている場合、 の重み は で、そのコストは です。ソリューションの総コストに対して 予算が与えられます。${\displaystyle S_{i}}$${\displaystyle c(S_{i})}$${\displaystyle e_{j}}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$${\displaystyle e_{j}}$${\displaystyle w_{i}(e_{j})}$${\displaystyle c_{i}(e_{j})}$${\displaystyle B}$

最大化します。(カバーされているセット内のカバーされている要素の加重合計を最大化します)。${\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}$

が適用されます(選択したセットのコストは を超えることはできません)。 ${\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B}$${\displaystyle B}$

${\displaystyle \sum _{i}y_{ij}\leq 1}$; (要素は最大 1 つのセットでのみカバーできます)。${\displaystyle e_{j}=1}$

${\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}}$; (少なくとも 1 つのセットが選択されている場合)。${\displaystyle y_{j}>0}$${\displaystyle e_{j}\in S_{i}}$

${\displaystyle y_{ij}\in \{0,1\}}$; (の場合、は集合 によってカバーされます)${\displaystyle y_{ij}=1}$${\displaystyle e_{j}}$${\displaystyle S_{i}}$

${\displaystyle x_{i}\in \{0,1\}}$(表紙に選択された場合) 。${\displaystyle x_{i}=1}$${\displaystyle S_{i}}$

このアルゴリズムは、残余コスト/重量の概念を使用します。残余コスト/重量は暫定的なソリューションに対して測定され、暫定的なソリューションによって得られるコスト/重量との差になります。

このアルゴリズムにはいくつかの段階があります。まず、貪欲アルゴリズムを使用してソリューションを見つけます。貪欲アルゴリズムの各反復では、要素の最大残余重量をこれらの要素の残余コストで割ったセットとセットの残余コストを含むセットが暫定ソリューションに追加されます。次に、最初のステップで得られたソリューションを、少数のセットを使用する最良のソリューションと比較します。最後に、すべての調査されたソリューションの中から最良のものを返します。このアルゴリズムは、近似率を達成します。^[6]${\displaystyle 1-1/e-o(1)}$

• 集合被覆問題は、できるだけ少ない集合ですべての要素を被覆することです。

• ヴァジラニ、ビジェイ V. (2001)。近似アルゴリズム。スプリンガー・フェルラーク。ISBN 978-3-540-65367-7。