k-ヒット集合のk-近似

コンピュータサイエンスにおいて、k-ヒッティングセットのk-近似は、重み付きヒッティングセットの近似アルゴリズムです。入力は、あるユニバースTの部分集合のコレクションSと、TからTの要素の重みと呼ばれる非負数へのマッピングWです。k-ヒッティングセットでは、 S内のセットのサイズはkより大きくすることはできません。つまり、 です。ここでの問題は、S内のすべてのセットにT 'の要素が含まれ、かつT 'のすべての要素の合計重みが可能な限り小さくなるような、Tの部分集合T 'を選択することです。 ${\displaystyle \forall i\in S:|i|\leq k}$

アルゴリズム

Sの各集合には価格が維持され、初期値は 0 である。Tの要素aについて、S ( a ) をaを含むSの集合の集合とする。アルゴリズムの実行中、以下の不変条件が満たされる。 ${\displaystyle j}$ ${\displaystyle p_{j}}$

${\displaystyle \forall a\in T:\sum _{j\in S(a)}p_{j}\leq W(a).\,}$

Tの要素aがタイトであるとは、 のときである。アルゴリズムの主要部分はループから構成される。S にTのタイトな要素を含まない集合が存在する限り、この集合の価格を上記の不変条件に違反しない範囲で可能な限り増加させる。このループが終了すると、すべての集合にタイトな要素が含まれる。これらのタイトな要素をすべて選択してヒット集合とする。 ${\displaystyle \Sigma _{j\in S(a)}p_{j}=W(a)}$

正確さ

このアルゴリズムは、ループの各反復処理において、 S内のいずれかのセットの価格が、Tの要素を1つ以上タイトにするのに十分なだけ増加するため、常に終了します。価格を一切増加できない場合は、ループは終了します。ループはSのすべてのセットの和集合に含まれる要素数を超える反復処理を行わないため、このアルゴリズムは多項式時間で実行されます。ループが終了すると、 S内のすべてのセットにTのタイト要素が含まれており、これらのタイト要素の集合が返されるため、ヒットセットが返されます。

任意のヒットセットT*と、アルゴリズムの不変式が成立する任意の価格について、ヒットセットの総重みは、 T*のすべての要素について、この要素を含むセットの価格の合計の上限、つまり となることに注意してください。これは不変式から導かれます。さらに、すべてのセットの価格は左辺に少なくとも1回出現する必要があるため、 となります。特に、この性質は最適なヒットセットにおいて当てはまります。 ${\displaystyle p_{1},\ldots ,p_{|S|}}$ ${\displaystyle \Sigma _{a\in T^{*}}\Sigma _{j\in S(a)}p_{j}\leq \Sigma _{a\in T^{*}}W(a)}$ ${\displaystyle \Sigma _{j\in S}p_{j}\leq \Sigma _{a\in T^{*}}W(a)}$

さらに、上記のアルゴリズムから返されるヒッティングセットHについて、 が成り立ちます。任意の価格は左辺に最大k回出現する可能性があるため（ SのサブセットにはTのk要素しか含まれないため）、 が成り立ちます。前の段落と組み合わせると が成り立ちます。ここで、T*は最適なヒッティングセットです。これはまさに、このアルゴリズムが k 近似アルゴリズムであることの保証です。 ${\displaystyle \Sigma _{a\in H}\Sigma _{j\in S(a)}p_{j}=\Sigma _{a\in H}W(a)}$ ${\displaystyle p_{j}}$ ${\displaystyle \Sigma _{a\in H}W(a)\leq k\cdot \Sigma _{j\in S}p_{j}}$ ${\displaystyle \Sigma _{a\in H}W(a)\leq k\cdot \Sigma _{a\in T^{*}}W(a)}$

線形計画法との関係

このアルゴリズムは、プライミング法とも呼ばれるプライマル・デュアル法の一例です。直感的には、線形計画法の双対アルゴリズムであると考えられます。説明については、https://algo.inria.fr/seminars/sem00-01/vazirani.html を参照してください。

参考文献

• クラインバーグ、Ｊ．タルドス、E. (2006)。アルゴリズム設計。ピアソン/アディソン＝ウェスリー。ISBN 0-321-29535-8。。
• S. Even ; R. Bar-Yehuda (1981). 「重み付き頂点被覆問題に対する線形時間近似アルゴリズム」. J. Algorithms . 2 (2): 198– 203. doi :10.1016/0196-6774(81)90020-1.
• Goemans, MX ; Williamson, DP (1997). 「近似アルゴリズムのためのプライマル・デュアル法とネットワーク設計問題への応用」Hochbaum, Dorit S. (編). 『NP困難問題のための近似アルゴリズム』 PWS Publishing Company. ISBN 0-534-94968-1。。