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)}$

このアルゴリズムは、プライシング法とも呼ばれるプライマルデュアル法のインスタンスです。直感的には、線形計画アルゴリズムの双対です。説明については、http://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。。