最大被覆問題
コンピュータサイエンスにおける問題

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

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

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

インスタンス: 数値とセットのコレクション。 け {\displaystyle k} S ＝ { S 1 、 S 2 、 … 、 S メートル } {\displaystyle S=\{S_{1},S_{2},\ldots ,S_{m}\}}
目的:カバーされる要素の数が最大化されるような集合のサブセットを見つけます。 S ′ ⊆ S {\displaystyle S'\subseteq S} | S ′ | ≤ k {\displaystyle \left|S'\right|\leq k} | ⋃ S i ∈ S ′ S i | {\displaystyle \left|\bigcup _{S_{i}\in S'}{S_{i}}\right|}

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

ILPの定式化

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

最大化する ∑ e j ∈ E y j {\displaystyle \sum _{e_{j}\in E}y_{j}} （カバーされた要素の合計を最大化する）
対象となる ∑ x i ≤ k {\displaystyle \sum {x_{i}}\leq k} （選択できるセットは 個まで） k {\displaystyle k}
∑ e j ∈ S i x i ≥ y j {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} （少なくとも1つのセットが選択されている場合） y j > 0 {\displaystyle y_{j}>0} e j ∈ S i {\displaystyle e_{j}\in S_{i}}
y j ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} （カバーされている場合） y j = 1 {\displaystyle y_{j}=1} e j {\displaystyle e_{j}}
x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} （表紙に選ばれた 場合） x i = 1 {\displaystyle x_{i}=1} S i {\displaystyle S_{i}}

貪欲アルゴリズム

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

既知の拡張機能

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

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

加重バージョン

重み付きバージョンでは、すべての要素に重み が与えられます 。課題は、重みが最大となる最大被覆率を見つけることです。基本バージョンは、すべての重みが である特殊なケースです。 e j {\displaystyle e_{j}} w ( e j ) {\displaystyle w(e_{j})} 1 {\displaystyle 1}

最大化します。(カバーされた要素の加重合計を最大化します)。 ∑ e ∈ E w ( e j ) ⋅ y j {\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}
;の対象となります(選択できるセットは 個までです)。 ∑ x i ≤ k {\displaystyle \sum {x_{i}}\leq k} k {\displaystyle k}
∑ e j ∈ S i x i ≥ y j {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} ; (少なくとも 1 つのセットが選択されている場合)。 y j > 0 {\displaystyle y_{j}>0} e j ∈ S i {\displaystyle e_{j}\in S_{i}}
y j ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} ; （その後はカバーされます） y j = 1 {\displaystyle y_{j}=1} e j {\displaystyle e_{j}}
x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (表紙に選択した場合) 。 x i = 1 {\displaystyle x_{i}=1} S i {\displaystyle S_{i}}

各段階における重み付き最大被覆率を求める貪欲アルゴリズムは、被覆されていない要素の重みが最大となる集合を選択する。このアルゴリズムは近似比[1]を達成する。 1 − 1 e {\displaystyle 1-{\frac {1}{e}}}

予算最大カバー範囲

予算付き最大被覆バージョンでは、各要素に重み が与えられているだけでなく、各セットにコスト も与えられます。これにより被覆内のセット数が制限される代わりに、予算が与えられます。この予算によって、選択可能な被覆の総コストが制限されます。 e j {\displaystyle e_{j}} w ( e j ) {\displaystyle w(e_{j})} S i {\displaystyle S_{i}} c ( S i ) {\displaystyle c(S_{i})} k {\displaystyle k} B {\displaystyle B} B {\displaystyle B}

最大化します。(カバーされた要素の加重合計を最大化します)。 ∑ e ∈ E w ( e j ) ⋅ y j {\displaystyle \sum _{e\in E}w(e_{j})\cdot y_{j}}
の対象となります。(選択したセットのコストは を超えることはできません)。 ∑ c ( S i ) ⋅ x i ≤ B {\displaystyle \sum {c(S_{i})\cdot x_{i}}\leq B} B {\displaystyle B}
∑ e j ∈ S i x i ≥ y j {\displaystyle \sum _{e_{j}\in S_{i}}x_{i}\geq y_{j}} ; (少なくとも 1 つのセットが選択されている場合)。 y j > 0 {\displaystyle y_{j}>0} e j ∈ S i {\displaystyle e_{j}\in S_{i}}
y j ∈ { 0 , 1 } {\displaystyle y_{j}\in \{0,1\}} ; （その後はカバーされます） y j = 1 {\displaystyle y_{j}=1} e j {\displaystyle e_{j}}
x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (表紙に選択した場合) 。 x i = 1 {\displaystyle x_{i}=1} S i {\displaystyle S_{i}}

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

一般化された最大カバレッジ

一般化最大被覆バージョンでは、各集合にはコスト がかかり、要素の重みとコストは、どの集合に被覆されているかによって異なります。つまり、が集合 に被覆されている場合、 の重みは 、そのコストは です。解の総コストには 予算が与えられます。 S i {\displaystyle S_{i}} c ( S i ) {\displaystyle c(S_{i})} e j {\displaystyle e_{j}} e j {\displaystyle e_{j}} S i {\displaystyle S_{i}} e j {\displaystyle e_{j}} w i ( e j ) {\displaystyle w_{i}(e_{j})} c i ( e j ) {\displaystyle c_{i}(e_{j})} B {\displaystyle B}

最大化します。(カバーされているセット内のカバーされている要素の加重合計を最大化します)。 ∑ e ∈ E , S i w i ( e j ) ⋅ y i j {\displaystyle \sum _{e\in E,S_{i}}w_{i}(e_{j})\cdot y_{ij}}
の対象となります。(選択したセットのコストは を超えることはできません)。 ∑ c i ( e j ) ⋅ y i j + ∑ c ( S i ) ⋅ x i ≤ B {\displaystyle \sum {c_{i}(e_{j})\cdot y_{ij}}+\sum {c(S_{i})\cdot x_{i}}\leq B} B {\displaystyle B}
∑ i y i j ≤ 1 {\displaystyle \sum _{i}y_{ij}\leq 1} ; (要素は最大 1 つのセットによってのみカバーされます)。 e j = 1 {\displaystyle e_{j}=1}
∑ S i x i ≥ y i j {\displaystyle \sum _{S_{i}}x_{i}\geq y_{ij}} ; (少なくとも 1 つのセットが選択されている場合)。 y j > 0 {\displaystyle y_{j}>0} e j ∈ S i {\displaystyle e_{j}\in S_{i}}
y i j ∈ { 0 , 1 } {\displaystyle y_{ij}\in \{0,1\}} ; （の場合、 は集合 によってカバーされます） y i j = 1 {\displaystyle y_{ij}=1} e j {\displaystyle e_{j}} S i {\displaystyle S_{i}}
x i ∈ { 0 , 1 } {\displaystyle x_{i}\in \{0,1\}} (表紙に選択した場合) 。 x i = 1 {\displaystyle x_{i}=1} S i {\displaystyle S_{i}}

一般化最大被覆アルゴリズム

このアルゴリズムは、残余コスト/重量の概念を採用しています。残余コスト/重量は暫定的な解決策と比較して測定され、暫定的な解決策によって得られるコスト/重量との差として表されます。

このアルゴリズムは複数の段階に分かれています。まず、貪欲アルゴリズムを用いて解を求めます。貪欲アルゴリズムの各反復において、暫定的な解に、要素の残差重量をこれらの要素の残差コストで割った値と、その集合の残差コストが最大となる集合が追加されます。次に、最初のステップで得られた解と、少数の集合を用いた最良解を比較します。最後に、検討したすべての解の中から最良の解を返します。このアルゴリズムは、近似率 を達成します。[6] 1 − 1 / e − o ( 1 ) {\displaystyle 1-1/e-o(1)}

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

注記

  1. ^ ab GL Nemhauser、LA Wolsey、ML Fisher. 劣モジュラー集合関数の最大化のための近似値の解析 I、Mathematical Programming 14 (1978)、265–294
  2. ^ Hochbaum, Dorit S. (1997). 「被覆問題とパッキング問題の近似：集合被覆、頂点被覆、独立集合、および関連問題」. Hochbaum, Dorit S. (編). 『NP困難問題のための近似アルゴリズム』. ボストン: PWS Publishing Company. pp.  94– 143. ISBN 978-053494968-6。
  3. ^ Feige, Uriel (1998年7月). 「近似集合被覆におけるln nの閾値」. Journal of the ACM . 45 (4). ニューヨーク州ニューヨーク市: Association for Computing Machinery: 634–652 . doi : 10.1145/285055.285059 . ISSN  0004-5411. S2CID  52827488.
  4. ^ Ali, Junade; Dyo, Vladimir (2017). 「所定の経路における車両のカバー範囲とモバイルセンサー配置：貪欲ヒューリスティックアプローチ」. 第14回国際電子ビジネス・電気通信合同会議議事録. 第2巻: WINSYS. pp.  83– 88. doi :10.5220/0006469800830088. ISBN 978-989-758-261-5。
  5. ^ Khuller, Samir; Moss, Anna; Naor, Joseph (Seffi) (1999). 「予算付き最大被覆問題」. Information Processing Letters . 70 : 39–45 . CiteSeerX 10.1.1.49.5784 . doi :10.1016/S0020-0190(99)00031-9. 
  6. ^ Cohen, Reuven; Katzir, Liran (2008). 「一般化最大被覆問題」. Information Processing Letters . 108 : 15–22 . CiteSeerX 10.1.1.156.2073 . doi :10.1016/j.ipl.2008.03.017. 

参考文献

Retrieved from "https://en.wikipedia.org/w/index.php?title=Maximum_coverage_problem&oldid=1316597962"