近似アルゴリズム

同義語:approximation algorithmapproximation algorithms

概要

近似アルゴリズム(approximation algorithm)とは、最適化問題に対して多項式時間で動き、どの入力でも最適値の決まった倍率(近似比)以内の値の解を返すアルゴリズムである。最適値は分からないので、極大マッチングの大きさ、線形計画緩和の最適値、重みの総和など、最適値を抑える量と解を比べる。頂点被覆は極大マッチングの端点で 2 倍以内、集合被覆は線形計画緩和の丸めで $f$ 倍以内($f$ は 1 つの要素を含む集合の個数の最大)、貪欲法で $H_n\approx\ln n$ 倍以内になり、後者は定数倍を除いて改善できない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 計算量理論, 線形計画法, マッチング(グラフ理論)

近似アルゴリズム(approximation algorithm)は、最適化問題に対し、多項式時間で動き、どの入力でも最適値の決まった倍率以内の値の解を返すアルゴリズムである。最適解を求めることが NP 困難な問題でも、「最適値の 2 倍以下」「最適値の半分以上」のような保証つきの解なら多項式時間で求められることが多い。この倍率を 近似比 という。
近似比を示すには、知らない最適値 $\mathrm{OPT}$ と、求めた解の値を比べる必要がある。そこで、$\mathrm{OPT}$ の側を下から(最小化なら)または上から(最大化なら)抑える量を用意し、それと解を比べる。極大マッチングの辺の本数、線形計画緩和の最適値、重みの総和がその典型である。
この記事では、近似比と近似スキームを定義し、頂点被覆の 2-近似、線形計画緩和の丸めによる集合被覆の $f$-近似、無作為なカットとその脱乱択化を証明する。主定理として、集合被覆の貪欲法が $H_n$-近似であることを証明し、その評価が改善できない例を挙げる。巡回セールスマン問題の近似は 巡回セールスマン問題、ナップサック問題の近似スキームは ナップサック問題 の記事で扱う。

定義と使える条件

最適化問題と近似比

最適化問題 は、各入力 $I$ に空でない実行可能解の集合と、各解 $s$ の値 $c(I,s)\ge0$ を与え、値を最小化(または最大化)する問題である。最適値を $\mathrm{OPT}(I)$ と書く。

  1. 最小化問題で $\alpha\ge1$ とする。多項式時間で動き、すべての入力 $I$ で $c(I,s)\le\alpha\,\mathrm{OPT}(I)$ を満たす解 $s$ を返すアルゴリズムを $\alpha$-近似アルゴリズム という。
  2. 最大化問題で $0<\alpha\le1$ とする。すべての入力で $c(I,s)\ge\alpha\,\mathrm{OPT}(I)$ を満たす解を返す多項式時間のアルゴリズムを $\alpha$-近似アルゴリズムという。
  3. $\alpha$ を 近似比 という。乱択アルゴリズムで、上の不等式が値の期待値 $E[c(I,s)]$ について成り立つものを 乱択 $\alpha$-近似アルゴリズム という。

この向きの約束(最小化は $\alpha\ge1$、最大化は $\alpha\le1$)は WS11 Definition 1.1 に従う。最大化でも $1/\alpha\ge1$ を近似比と呼ぶ文献がある。

近似スキーム
  1. 各 $\varepsilon>0$ に対しアルゴリズム $A_\varepsilon$ があり、$A_\varepsilon$ が $(1+\varepsilon)$-近似(最小化)または $(1-\varepsilon)$-近似(最大化)であるとき、$\{A_\varepsilon\}$ を 多項式時間近似スキーム(PTAS)という。$A_\varepsilon$ の計算時間は $1/\varepsilon$ に任意に依存してよい。
  2. さらに $A_\varepsilon$ の計算時間が入力の長さと $1/\varepsilon$ の多項式で抑えられるとき、完全多項式時間近似スキーム(FPTAS)という。
集合被覆問題と頂点被覆問題
  1. 集合被覆問題:有限集合 $U=\{e_1,\dots,e_n\}$、その部分集合 $S_1,\dots,S_m$(和集合が $U$)、重み $w_j\ge0$ が与えられる。$\bigcup_{j\in J}S_j=U$ となる $J\subset\{1,\dots,m\}$(被覆)で、$w(J)=\sum_{j\in J}w_j$ が最小のものを求める。$f$ を 1 つの要素を含む集合の個数の最大値、$g=\max_j\lvert S_j\rvert$ とおく。
  2. 頂点被覆問題:グラフ $G=(V,E)$ と頂点の重み $w_v\ge0$ に対し、すべての辺の少なくとも一方の端点を含む頂点の集合 $C$(頂点被覆)で、重みの和が最小のものを求める。辺を要素、頂点 $v$ に接する辺の集合を $S_v$ とみると集合被覆問題で、各辺は両端の 2 つの集合に属するので $f=2$ である。

頂点被覆の判定版は NP完全で(NP完全 の定理「独立集合・クリーク・頂点被覆の NP完全性」)、それを特別な場合に含む集合被覆問題も NP 困難である。$H_k=1+\frac12+\cdots+\frac1k$ は 調和数 で、$\ln(k+1)\le H_k\le1+\ln k$ を満たす。
この記事の結論を使える条件をまとめる。

  1. 最悪の場合の保証:近似比はすべての入力で成り立つ評価で、入力の分布を仮定しない。
  2. 最適値の代わりの評価:$\mathrm{OPT}$ は分からないので、最小化では $\mathrm{OPT}$ 以下の量、最大化では $\mathrm{OPT}$ 以上の量と解を比べる。
  3. 重みが非負:線形計画の丸め、貪欲法、無作為なカットの評価は $w_j\ge0$ を使う(節「使える条件と反例」)。
  4. 乱択の近似比は期待値:1 回の出力は保証を下回りうる。

公式の表

公式使える条件根拠
極大マッチング $M$ の端点:被覆で、大きさ $2\lvert M\rvert\le2\,\mathrm{OPT}$重みなしの頂点被覆thm-aa-vc-matching
$Z_{\mathrm{LP}}\le\mathrm{OPT}$最小化の線形計画緩和lem-aa-lp
$x_j^\ast\ge1/f$ の集合を採る:$w(J)\le f\,Z_{\mathrm{LP}}\le f\,\mathrm{OPT}$$w_j\ge0$thm-aa-lp-round
重み付き頂点被覆:$x_v^\ast\ge\frac12$ の頂点で 2-近似$w_v\ge0$thm-aa-lp-round($f=2$)
貪欲法:$w(J)\le H_n\,\mathrm{OPT}$$w_j\ge0$thm-aa-greedy
貪欲法:$w(J)\le H_g\,Z_{\mathrm{LP}}$$w_j\ge0$WS11 Theorem 1.12(証明しない)
無作為なカット:$E[\text{値}]=W/2\ge\mathrm{OPT}/2$辺の重み $\ge0$、$W$ は総和prop-aa-cut-half
条件付き期待値の方法:決定的に値 $\ge W/2$同上prop-aa-derand
最大カットの $0.878$-近似辺の重み $\ge0$半正定値計画 の定理「Goemans–Williamson の近似」
MAX-3SAT の $7/8$-近似各節が相異なる 3 変数PCP定理 の命題「ランダムな割り当て」
ナップサック問題の FPTAS価値が正ナップサック問題 の定理「価値を丸める近似」
距離付きの巡回セールスマン問題の $3/2$-近似三角不等式巡回セールスマン問題 の定理「Christofides の方法」

主定理と証明

頂点被覆と極大マッチング

辺の集合 $M$ で、どの 2 本も端点を共有しないものを マッチング といい、どの辺を加えてもマッチングでなくなるものを 極大 という(マッチング(グラフ理論))。辺を順に見て、それまでに選んだ辺と端点を共有しなければ選ぶ、という手順で極大マッチングが $O(\lvert E\rvert)$ 程度の手間で得られる。

極大マッチングによる 2-近似

$M$ をグラフ $G$ の極大マッチングとし、$M$ の辺の端点全体を $C$ とする。$C$ は頂点被覆で、$\lvert C\rvert=2\lvert M\rvert\le2\,\mathrm{OPT}$ である($\mathrm{OPT}$ は頂点被覆の最小の大きさ)。

下界はマッチングの大きさ

辺 $e$ が $C$ の頂点を端点にもたないとすると、$e$ は $M$ のどの辺とも端点を共有しないので、$M\cup\{e\}$ はマッチングで、$M$ の極大性に反する。よって $C$ は頂点被覆である。$M$ の辺は端点を共有しないので $\lvert C\rvert=2\lvert M\rvert$ である。一方、どの頂点被覆も $M$ の各辺の端点を少なくとも 1 つ含み、$M$ の辺の端点は互いに異なるので、頂点被覆は $\lvert M\rvert$ 個以上の頂点を含む。よって $\mathrm{OPT}\ge\lvert M\rvert$ である。

完全 2 部グラフ $K_{k,k}$ では極大マッチングは $k$ 本で出力は $2k$ 頂点、片側の $k$ 頂点が最小の頂点被覆なので、比はちょうど $2$ になる。

線形計画緩和の丸め

集合被覆問題は、$x_j=1$ を「$S_j$ を採る」と読むと整数計画問題になる。$x_j\in\{0,1\}$ を $x_j\ge0$ に緩めた
$$ \text{(LP)}\quad\min\sum_{j=1}^mw_jx_j\quad\text{条件 }\sum_{j:\,e_i\in S_j}x_j\ge1\ (i=1,\dots,n),\ x_j\ge0 $$
を 線形計画緩和 といい、その最適値を $Z_{\mathrm{LP}}$ と書く(整数計画法)。(LP) は 線形計画法 の問題なので多項式時間で解ける。

緩和は最適値の下界

$Z_{\mathrm{LP}}\le\mathrm{OPT}$ である。

最適な被覆 $J$ に対し、$j\in J$ なら $x_j=1$、そうでなければ $x_j=0$ とおくと、各要素 $e_i$ を含む $S_j$ が $J$ に 1 つはあるので (LP) の条件を満たし、目的関数の値は $w(J)=\mathrm{OPT}$ である。(LP) の最小値はこれ以下である。

決定的な丸めによる f-近似

$x^\ast$ を (LP) の最適解とし、$J=\{j\mid x_j^\ast\ge1/f\}$ とする。$J$ は被覆で、$w(J)\le f\,Z_{\mathrm{LP}}\le f\,\mathrm{OPT}$ である。

要素 $e_i$ を含む集合は $f$ 個以下なので、条件 $\sum_{j:\,e_i\in S_j}x_j^\ast\ge1$ の左辺の項は $f$ 個以下で、そのうち少なくとも 1 つは $1/f$ 以上である。その $j$ は $J$ に入るので、$e_i$ は覆われる。$j\in J$ なら $1\le fx_j^\ast$ で、$w_j\ge0$ なので
$$ w(J)=\sum_{j\in J}w_j\le\sum_{j\in J}w_jfx_j^\ast\le f\sum_{j=1}^mw_jx_j^\ast=f\,Z_{\mathrm{LP}} $$
である。最後に lem-aa-lp を使う。

頂点被覆では $f=2$ なので、重み付きでも $x_v^\ast\ge\frac12$ の頂点を採れば 2-近似になる(WS11 Lemma 1.5・Theorem 1.6)。比 $w(J)/Z_{\mathrm{LP}}$ は入力ごとに計算できるので、その入力での解の質を事後に確かめられる。

集合被覆の貪欲法

貪欲法

$J=\emptyset$、未被覆の要素の集合を $R=U$ として始める。$R\ne\emptyset$ の間、$S_j\cap R\ne\emptyset$ となる $j$ のうち、比 $w_j/\lvert S_j\cap R\rvert$(まだ覆われていない要素 1 個あたりの重み)が最小のものを 1 つ選び、$J$ に加えて $R$ から $S_j$ を除く。$R=\emptyset$ になったら $J$ を出力する。

各回で $R$ は 1 つ以上減るので、回数は $n$ 以下で、多項式時間で止まる。

貪欲法の近似比

重みが非負の集合被覆問題で、貪欲法の出力 $J$ は $w(J)\le H_n\,\mathrm{OPT}$ を満たす。すなわち貪欲法は $H_n$-近似アルゴリズムである(WS11 Theorem 1.11)。

1 回ごとに、残りの要素 1 個あたり OPT/n_k 以下を払う

貪欲法が $\ell$ 回で止まるとし、$k$ 回目の開始時の未被覆の要素の個数を $n_k$ とする。$n_1=n$、$n_{\ell+1}=0$ である。$k$ 回目の開始時の未被覆の要素の集合を $R_k$、$k$ 回目に選ぶ集合を $S_{j_k}$ とする。
手順 1:各回の比は $\mathrm{OPT}/n_k$ 以下。 最適な被覆を $O$ とし、$O'=\{j\in O\mid S_j\cap R_k\ne\emptyset\}$ とおく。$O$ は $R_k$ を覆うので $O'$ は空でなく、$\sum_{j\in O'}\lvert S_j\cap R_k\rvert\ge n_k$ である。もし $j\in O'$ のすべてで $w_j>\frac{\mathrm{OPT}}{n_k}\lvert S_j\cap R_k\rvert$ なら、足し合わせて
$$ \mathrm{OPT}\ge\sum_{j\in O'}w_j>\frac{\mathrm{OPT}}{n_k}\sum_{j\in O'}\lvert S_j\cap R_k\rvert\ge\mathrm{OPT} $$
となり矛盾する(左の不等号は $w_j\ge0$ による)。よって $w_j/\lvert S_j\cap R_k\rvert\le\mathrm{OPT}/n_k$ となる $j\in O'$ があり、貪欲法の選ぶ $j_k$ の比はその値以下である。
手順 2:1 回の重みの評価。 $k$ 回目に覆われる要素は $\lvert S_{j_k}\cap R_k\rvert=n_k-n_{k+1}$ 個なので、手順 1 から
$$ w_{j_k}\le(n_k-n_{k+1})\frac{\mathrm{OPT}}{n_k}=\mathrm{OPT}\sum_{i=n_{k+1}+1}^{n_k}\frac1{n_k}\le\mathrm{OPT}\sum_{i=n_{k+1}+1}^{n_k}\frac1i $$
である。最後の不等号は、和の各項で $i\le n_k$ だからである。
手順 3:足し合わせる。 $k=1,\dots,\ell$ で足すと、右辺の和の範囲 $(n_{k+1},n_k]$ は $(0,n]$ を重ならずに分けるので
$$ w(J)=\sum_{k=1}^\ell w_{j_k}\le\mathrm{OPT}\sum_{i=1}^n\frac1i=H_n\,\mathrm{OPT} $$
である。

貪欲法の評価は改善できない

$n\ge2$、$0<\varepsilon<\frac1n$ とし、$U=\{e_1,\dots,e_n\}$、$S_0=U$(重み $1+\varepsilon$)、$S_i=\{e_i\}$(重み $1/i$、$i=1,\dots,n$)とする。貪欲法は $S_n,S_{n-1},\dots,S_1$ を選び、$w(J)=H_n$ である。$\mathrm{OPT}=1+\varepsilon$ なので、比 $H_n/(1+\varepsilon)$ は $\varepsilon\to0$ で $H_n$ に近づく。

$e_n,\dots,e_{k+1}$ が覆われ、$R=\{e_1,\dots,e_k\}$ のときを考える。$S_0$ の比は $(1+\varepsilon)/k$、$S_i$($i\le k$)の比は $1/i$ で、最小は $S_k$ の $1/k$ である($1/k< (1+\varepsilon)/k$)。よって貪欲法は $S_k$ を選ぶ。これを $k=n,\dots,1$ と繰り返すので $w(J)=\sum_{i=1}^n\frac1i=H_n$ である。被覆は $S_0$ を含むか、$S_1,\dots,S_n$ をすべて含むので、重みは $\min\{1+\varepsilon,H_n\}$ 以上で、$\varepsilon<\frac1n$ と $n\ge2$ なら $1+\varepsilon< H_n$ なので $\mathrm{OPT}=1+\varepsilon$ である($n=1$ なら貪欲法は最適)。

図: 左は集合被覆の貪欲法が改善できない例(n=4)で、横軸は選ぶ順番、縦軸は払った重みの累計。貪欲法は 1/4、1/3、1/2、1 の重みの 1 点集合を順に選び、累計は H_4 = 25/12 に達する。最適な被覆は全体の集合 1 つで重み 1.01(水平の破線)。右は n を 1 から 10^4 まで動かしたときの H_n と ln n、ln n + 1 のグラフで、H_n は 2 つの曲線の間にある。 図: 左は集合被覆の貪欲法が改善できない例(n=4)で、横軸は選ぶ順番、縦軸は払った重みの累計。貪欲法は 1/4、1/3、1/2、1 の重みの 1 点集合を順に選び、累計は H_4 = 25/12 に達する。最適な被覆は全体の集合 1 つで重み 1.01(水平の破線)。右は n を 1 から 10^4 まで動かしたときの H_n と ln n、ln n + 1 のグラフで、H_n は 2 つの曲線の間にある。
近似比 $H_n\approx\ln n$ は、定数倍を除いて最良である。ある定数 $c>0$ について、重みなしの集合被覆に $c\ln n$-近似アルゴリズムがあれば P $=$ NP となる(WS11 Theorem 1.14。この記事では証明しない)。

無作為な解と脱乱択化

辺の重み $w_e\ge0$ のグラフ $G=(V,E)$ で、頂点の集合 $A\subset V$ に対し、$A$ と $V\setminus A$ を結ぶ辺の重みの和を カットの値 といい、その最大を求める問題を 最大カット問題 という。$W=\sum_ew_e$ とおく。

無作為なカット

各頂点を独立に確率 $\frac12$ で $A$ に入れると、カットの値の期待値は $W/2$ で、$W/2\ge\mathrm{OPT}/2$ である。これは乱択 $\frac12$-近似アルゴリズムである(WS11 Theorem 5.3)。

辺 $uv$ がカットに入るのは $u,v$ の一方だけが $A$ に入るときで、その確率は $\frac12\cdot\frac12+\frac12\cdot\frac12=\frac12$ である。期待値の線形性 から期待値は $\sum_ew_e/2=W/2$ である。どのカットの値も $W$ 以下なので $\mathrm{OPT}\le W$ である。

条件付き期待値の方法

頂点を $v_1,\dots,v_N$ と並べ、$i=1,\dots,N$ の順に、$v_i$ を、すでに置いた頂点のうち $v_i$ と隣り合うものとの辺の重みの和が大きいほうの側の 反対側 に置く(同点ならどちらでもよい)。得られるカットの値は $W/2$ 以上である。

期待値を減らさずに 1 頂点ずつ決める

要点:$v_1,\dots,v_i$ を置き、残りを無作為に置いたときの値の期待値 $\Phi_i$ が $i$ について減らないことを示す。

詳しい証明を開く

$v_1,\dots,v_i$ の置き場所を固定し、残りの頂点を独立に確率 $\frac12$ ずつで置いたときのカットの値の期待値を $\Phi_i$ とする。$\Phi_0=W/2$ で、$\Phi_N$ は得られるカットの値である。両端が置かれた辺はカットに入るかどうかが決まっており、一方でもまだ置かれていない辺は確率 $\frac12$ でカットに入る。$v_i$ を置く前の期待値 $\Phi_{i-1}$ は、$v_i$ を $A$ 側に置いた場合と反対側に置いた場合の期待値の平均である。$v_i$ とまだ置いていない頂点を結ぶ辺の寄与はどちらの場合も重みの半分なので、両者の差は $v_i$ とすでに置いた頂点を結ぶ辺だけから生じる。隣の重みが大きいほうの側の反対側に置けば、それらの辺のうちカットに入る重みが大きいほうになるので、2 つの期待値の大きいほうが選ばれる。よって $\Phi_i\ge\Phi_{i-1}$ で、$\Phi_N\ge\Phi_0=W/2$ である。

同じ方法は、期待値を計算できる多くの乱択の近似アルゴリズムを決定的なものに替える(WS11 §5.2)。最大カット問題では、半正定値計画 による $0.878$-近似が知られている。

計算の手順

  1. 最適値の代わりの評価を探す。最小化なら $\mathrm{OPT}$ 以下の量(マッチングの大きさ、線形計画緩和の値 $Z_{\mathrm{LP}}$、双対問題の実行可能解の値)、最大化なら $\mathrm{OPT}$ 以上の量(重みの総和 $W$ など)を用意する。
  2. その評価と比べられる解を作る。緩和の解を丸める、貪欲に選ぶ、無作為に選ぶなど。
  3. すべての入力で比を示す。重みの非負性などの仮定を使った箇所を確かめる。
  4. 比が改善できない入力を探す。評価がその入力で等号に近ければ、その解析ではこれ以上よくならない。
  5. 困難性の結果と比べる。P $\ne$ NP などの仮定のもとで、それより良い比が不可能かを調べる。
  6. 個々の入力では事後の比を計算する。$w(J)/Z_{\mathrm{LP}}$ のような比は保証よりずっと小さいことが多い。

例題

5 頂点の閉路の頂点被覆

閉路 $C_5$(重みはすべて $1$)の最小の頂点被覆の大きさは $3$ である($2$ 頂点は $4$ 本以下の辺しか覆わない)。辺を順に見て極大マッチングを作ると $2$ 本になり、出力は $4$ 頂点で $4\le2\cdot3$ である。(LP) の最適解はすべて $x_v^\ast=\frac12$ で $Z_{\mathrm{LP}}=\frac52$ である(各辺に $y_e=\frac12$ を置くと双対問題の実行可能解で値 $\frac52$ なので、$\frac52$ より小さくできない。$y_e>0$ なので 線形計画法 の定理「相補性条件」により、最適解では各辺の条件 $x_u+x_v\ge1$ が等号になり、奇数の閉路を一周すると $x_v^\ast=\frac12$ に決まる)。丸めると $5$ 頂点すべてを採り、$5\le2Z_{\mathrm{LP}}=5\le2\cdot3$ で、thm-aa-lp-round の 1 つ目の不等式が等号になる。

貪欲法と丸めの比較

$U=\{1,\dots,6\}$、$S_1=\{1,2,3\}$、$S_2=\{4,5,6\}$、$S_3=\{1,2,4,5\}$、重みはすべて $1$ とする。貪欲法は最初に $4$ 要素を覆う $S_3$ を選び、残りの $3$ と $6$ のために $S_1$ と $S_2$ を選んで $w(J)=3$ になる。最適は $\{S_1,S_2\}$ で $\mathrm{OPT}=2$ である。$3$ と $6$ は $1$ つの集合にしか含まれないので (LP) で $x_1=x_2=1$ が必要で、$Z_{\mathrm{LP}}=2$、$f=2$ である。丸めは $\{S_1,S_2\}$ を返して最適になる。貪欲法の比 $1.5$ は保証 $H_6=2.45$ より小さい。

改善できない例の数値

prop-aa-greedy-tight で $n=4$、$\varepsilon=\frac1{100}$ とする。最初の比は $S_0$ が $1.01/4=0.2525$、$S_4$ が $1/4=0.25$ で $S_4$ が選ばれ、以下 $S_3,S_2,S_1$ と選ばれる。$w(J)=1+\frac12+\frac13+\frac14=\frac{25}{12}\approx2.083$、$\mathrm{OPT}=1.01$ で、比は約 $2.063$、保証 $H_4=\frac{25}{12}$ にほぼ等しい。

完全グラフ K4 の最大カット

$K_4$(頂点 $1,2,3,4$、重みはすべて $1$、$W=6$)に prop-aa-derand を当てる。$1$ をどちらかの側に置き、$2$ は $1$ の反対側、$3$ は $1$ と $2$ の重みが同点なので $1$ の反対側($2$ と同じ側)、$4$ は $1$ の側の隣($1$ 本)と $2,3$ の側の隣($2$ 本)を比べて $1$ の側に置く。$\{1,4\}$ と $\{2,3\}$ のカットの値は $4\ge W/2=3$ で、$K_4$ の最大カット $4$ に等しい。

線形計画緩和の限界

完全グラフ $K_N$ の頂点被覆の最小の大きさは $N-1$ である($2$ 頂点を除くと、その間の辺が覆われない)。一方、すべて $x_v=\frac12$ は (LP) の実行可能解で、各辺の条件を足すと $(N-1)\sum_vx_v\ge\binom N2$ なので $Z_{\mathrm{LP}}=\frac N2$ である。比 $\mathrm{OPT}/Z_{\mathrm{LP}}=2-\frac2N$ は $N\to\infty$ で $2$ に近づく($N=5$ で $1.6$、$N=8$ で $1.75$)。$Z_{\mathrm{LP}}$ と比べる解析だけでは、頂点被覆で $2-\frac2N$ より良い比は示せない。

使える条件と反例

各行は条件を 1 つだけ外し、ほかの条件は保つ。

外す条件例成り立たなくなる結論
マッチングが極大道 $a$–$b$–$c$–$d$ で $M=\{ab\}$端点 $\{a,b\}$ は辺 $cd$ を覆わない
丸めの閾値が $1/f$ 以下$U=\{e\}$、$S_1=S_2=S_3=\{e\}$(重みはすべて $1$)、$x^\ast=(\frac13,\frac13,\frac13)$ を閾値 $\frac12$ で丸める何も選ばれず、被覆にならない
比の分母が未被覆の要素の個数集合全体の大きさ $\lvert S_j\rvert$ で比を測る(ex-aa-static)比 $5$ が $H_{20}\approx3.60$ を超える
重みが非負三角形で $w_{12}=w_{13}=-1$、$w_{23}=2$無作為なカットの期待値 $W/2=0$、$\mathrm{OPT}=1$ で比が $0$
比の分母を集合全体の大きさにする

$k=10$、$U=\{1,\dots,20\}$ とし、$B_i=\{1,\dots,10\}\cup\{10+i\}$($i=1,\dots,10$)、$D_1=\{1,\dots,10\}$、$D_2=\{11,\dots,20\}$、重みはすべて $1$ とする。まだ覆われていない要素を含む集合のうち $w_j/\lvert S_j\rvert$ が最小のもの(大きさ $11$ の $B_i$)を選び続けると、$B_1,\dots,B_{10}$ の $10$ 個を選ぶ。$\mathrm{OPT}=2$($D_1,D_2$)なので比は $5$ で、$H_{20}\approx3.598$ を超える。正しい貪欲法は $B_1$ のあと、未被覆の $9$ 要素をすべて含む $D_2$ を選び、$2$ 個で最適になる。thm-aa-greedy の手順 2 は、覆った要素の個数 $n_k-n_{k+1}$ を比の分母に使っている。

よくある誤り

誤り正しくはなぜ
近似比の向きを取り違える最小化では $\alpha\ge1$、最大化では $\alpha\le1$ とする約束と、最大化でも $1/\alpha\ge1$ を書く約束があるdef-aa-ratio
$Z_{\mathrm{LP}}$ を最適値と思う最小化では $Z_{\mathrm{LP}}\le\mathrm{OPT}$ で、差がありうるex-aa-gap
補集合を取っても近似比が保たれると思う頂点被覆の補集合は独立集合だが、頂点被覆の 2-近似から独立集合の近似は得られない。$N/2$ 本の辺が互いに離れているグラフでは、thm-aa-vc-matching の出力は全頂点で、補集合は空集合、最大の独立集合は $N/2$ 頂点左の例
NP 困難なら近似も同じく難しいと思うナップサック問題には FPTAS があるが、集合被覆には $c\ln n$ より良い比が P $\ne$ NP のもとで不可能で、問題ごとに大きく違うWS11 Theorem 1.14
乱択の近似比を 1 回の出力の保証と思う期待値の保証なので、繰り返して最良を採るか、脱乱択化するprop-aa-derand

補足

頂点被覆では、$\alpha<10\sqrt5-21\approx1.36$ の $\alpha$-近似アルゴリズムがあれば P $=$ NP であり、一意ゲーム予想(Unique Games予想)を仮定すると定数 $\alpha<2$ の近似アルゴリズムがあれば P $=$ NP である(WS11 Theorems 1.15・1.16。証明しない)。2 より小さい定数の近似比をもつアルゴリズムは、WS11 の時点(2011 年)では知られていない。
近似スキームの有無も問題によって違う。ナップサック問題には FPTAS がある(ナップサック問題)。最大カットは、$\alpha>16/17\approx0.941$ の $\alpha$-近似アルゴリズムがあれば P $=$ NP となるので(WS11 Theorem 6.10)、P $\ne$ NP なら PTAS をもたない。MAX-3SAT も同様である(PCP定理 の系「MAX-3SAT の近似困難性」)。

関連項目

参考文献

[1]
David P. Williamson; David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, 頁は著者公開の電子版(2011)のもの:§1.1:Definitions 1.1・1.2 と Theorem 1.3(pp. 14–15)、§1.2:(1.1)・(1.2)(p. 18)、§1.3:Lemma 1.5・Theorem 1.6(pp. 19–20)、§1.6:Algorithm 1.2 と Theorem 1.11(pp. 25–26)、Theorem 1.12(pp. 26–27)、Theorems 1.14–1.16(p. 28)、Definition 3.4(p. 67)、§5.1:Theorem 5.3(p. 107)、§5.2(pp. 108–109)、Theorem 6.10(p. 147)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する