近似アルゴリズム(approximation algorithm)とは、最適化問題に対して多項式時間で動き、どの入力でも最適値の決まった倍率(近似比)以内の値の解を返すアルゴリズムである。最適値は分からないので、極大マッチングの大きさ、線形計画緩和の最適値、重みの総和など、最適値を抑える量と解を比べる。頂点被覆は極大マッチングの端点で 2 倍以内、集合被覆は線形計画緩和の丸めで $f$ 倍以内($f$ は 1 つの要素を含む集合の個数の最大)、貪欲法で $H_n\approx\ln n$ 倍以内になり、後者は定数倍を除いて改善できない。
前提知識: 計算量理論, 線形計画法, マッチング(グラフ理論)
近似アルゴリズム(approximation algorithm)は、最適化問題に対し、多項式時間で動き、どの入力でも最適値の決まった倍率以内の値の解を返すアルゴリズムである。最適解を求めることが NP 困難な問題でも、「最適値の 2 倍以下」「最適値の半分以上」のような保証つきの解なら多項式時間で求められることが多い。この倍率を 近似比 という。
近似比を示すには、知らない最適値 $\mathrm{OPT}$ と、求めた解の値を比べる必要がある。そこで、$\mathrm{OPT}$ の側を下から(最小化なら)または上から(最大化なら)抑える量を用意し、それと解を比べる。極大マッチングの辺の本数、線形計画緩和の最適値、重みの総和がその典型である。
この記事では、近似比と近似スキームを定義し、頂点被覆の 2-近似、線形計画緩和の丸めによる集合被覆の $f$-近似、無作為なカットとその脱乱択化を証明する。主定理として、集合被覆の貪欲法が $H_n$-近似であることを証明し、その評価が改善できない例を挙げる。巡回セールスマン問題の近似は 巡回セールスマン問題、ナップサック問題の近似スキームは ナップサック問題 の記事で扱う。
最適化問題 は、各入力 $I$ に空でない実行可能解の集合と、各解 $s$ の値 $c(I,s)\ge0$ を与え、値を最小化(または最大化)する問題である。最適値を $\mathrm{OPT}(I)$ と書く。
この向きの約束(最小化は $\alpha\ge1$、最大化は $\alpha\le1$)は WS11 Definition 1.1 に従う。最大化でも $1/\alpha\ge1$ を近似比と呼ぶ文献がある。
頂点被覆の判定版は NP完全で(NP完全 の定理「独立集合・クリーク・頂点被覆の NP完全性」)、それを特別な場合に含む集合被覆問題も NP 困難である。$H_k=1+\frac12+\cdots+\frac1k$ は 調和数 で、$\ln(k+1)\le H_k\le1+\ln k$ を満たす。
この記事の結論を使える条件をまとめる。
| 公式 | 使える条件 | 根拠 |
|---|---|---|
| 極大マッチング $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)$ 程度の手間で得られる。
$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) の最小値はこれ以下である。
$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)。
貪欲法が $\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 つの曲線の間にある。
近似比 $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$ 以上である。
要点:$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$-近似が知られている。
閉路 $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}$ にほぼ等しい。
$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 の近似困難性」)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する