近似アルゴリズム — 厳密を諦めて保証を取る

最適解を諦める代わりに「最悪でも◯倍以内」という値札を付ける技術。近似比の定義から、貪欲アルゴリズムの保証を最後まで証明する手つき、巡回セールスマンで三角不等式の有無が結論をひっくり返す理由までを前提知識ゼロで積み上げます。

比喩: 完璧な配送順を待つ間に、日が暮れる

トラック1台で30軒を回る順番を、走行距離が最小になるように決めたい。回り方の総数は $29!/2 \approx 4.4 \times 10^{30}$ 通りです。総当たりのコードは10行で書けますが、答えが返るころには会社がなくなっています。

一方、営業所のベテランは10秒で「だいたいこの順」と言います。速い。ただし、その順が最善より2割悪いのか3倍悪いのかは、本人も含めて誰も知りません。

近似アルゴリズムは、この2つの間に立ちます。多項式時間で終わり、しかも出てきた答えに「最悪でも最適解の◯倍以内」という値札が付く。厳密さを手放す代わりに、手放した量の上限を数学的に押さえる。これがこの分野の取引条件です。

なぜそんな取引が要るのかはNP完全を1からで見たとおりで、巡回セールスマンもスケジューリングもビンパッキングも、多項式時間で厳密に解ける見込みがありません。「解けない」と分かった後の身の振り方として、いちばん筋の通った選択肢がこれです。

近似比 — 「だいたい合ってる」を数にする

まず「近い」を定義しないと始まりません。距離やコストを小さくしたい最小化問題で考えます。入力 $I$ に対してアルゴリズムが返す解のコストを $\mathrm{ALG}(I)$、最適解のコストを $\mathrm{OPT}(I)$ と書きます。

式(1)は「どんな入力を持ってこられても、答えのコストは最適の $\rho$ 倍を超えない」と言っています。$\max_I$ は「意地悪な人が最悪の入力を選んでくる」という意味で、そこでも成り立つ $\rho$ を近似比と呼びます。$\rho=2$ のアルゴリズムを「2-近似」と言い、$\rho$ は必ず1以上、1に近いほど良いアルゴリズムです。

利益や被覆数を大きくしたい最大化問題では向きが逆になり、$\mathrm{ALG} \ge \mathrm{OPT}/\rho$ と書きます。どちらの向きでも、ここで最初の関門にぶつかります。

最適解を計算できないから近似しているのに、最適解との比をどうやって保証するのか。

保証の作り方 — 最適解を知らずに最適解と比べる

種明かしは、$\mathrm{OPT}$ そのものではなく、$\mathrm{OPT}$ より下にあると分かっている量を経由することです。これを下界（lower bound）と呼びます。

式(2)を平たく言い換えると「アルゴリズムの答えは、自分で計算できる量 $\mathrm{LB}$ の $c$ 倍以内。そしてその $\mathrm{LB}$ は最適解以下。ゆえに答えは最適の $c$ 倍以内」。ポイントは、真ん中の $\mathrm{LB}$ が手元で扱える量だという点です。左の不等式はアルゴリズムの動作を追えば示せ、右の不等式は問題の性質から示せる。最適解が何なのかを一度も特定しないまま、最適解との距離が言えてしまうわけです。

近似アルゴリズムの論文の大半は、新しい貪欲手続きを考える時間より、良い下界を見つける時間のほうが長い。以降に出てくる証明は全部この型なので、式(2)だけ頭に置いておけば読み通せます。

そもそもなぜ厳密解を諦めるのか、桁の感覚を先に取っておきます。

貪欲の証明を1本、最後まで見る — 頂点被覆

頂点被覆問題は、グラフのすべての辺について、その両端の少なくとも一方が選ばれているような頂点の集合を、できるだけ少ない頂点数で作る問題です。交差点に監視カメラを置いてすべての道路を見張る、と思えば十分です。これはNP困難で、素朴な発想としては「次数がいちばん大きい頂点から取る」貪欲が浮かびますが、実はこれは $\log n$ 倍まで悪くなる入力が作れます。

代わりに、拍子抜けするほど単純な手続きが2-近似になります。

1. まだ覆われていない辺 $(u,v)$ を1本、適当に選ぶ
2. 両端 $u$ と $v$ を両方解に入れる
3. $u$ か $v$ に接する辺をすべて消す。辺がなくなるまで1へ戻る

なぜ2-近似なのかを、式(2)の型に流し込みます。手続きの中で選んだ辺の集まりを $M$ とします。$M$ の2辺が端点を共有することはありません。辺を選んだ瞬間に、その端点に接する辺は全部消しているからです。こういう「互いに端点を共有しない辺の集まり」をマッチングと呼びます。

• 上界: 出力 $C$ は $M$ の各辺から2頂点ずつ入れたものなので $|C| = 2|M|$。
• 下界: どんな頂点被覆であっても、$M$ に入っている各辺を覆うために、その辺の端点を最低1つは含まなければなりません。$M$ の辺は端点を共有しないので、その「最低1つ」は辺ごとに別の頂点です。ゆえに $\mathrm{OPT} \ge |M|$。

2つを合わせて $|C| = 2|M| \le 2\,\mathrm{OPT}$。$\mathrm{LB} = |M|$ を挟んだだけで、2-近似が出ました。

def vertex_cover_2approx(edges):          # edges: [(u, v), ...]
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:   # まだ覆われていない辺
            cover.add(u)                        # 両端を「両方」入れる
            cover.add(v)
    return cover

「両方入れる」のは一見無駄ですが、そこが保証の源泉です。「次数が大きいほうだけ入れる」と賢そうに改造した瞬間、上の下界の議論が壊れて2-近似は主張できなくなります。改造したら証明も作り直す、これは以降ずっと効いてくる原則です。

ちなみにこの2という数字はほぼ限界で、1.3606倍より良い近似はNP困難（Dinur–Safra, 2005）、さらにUnique Games予想を認めるなら $2-\varepsilon$ すら不可能とされています。教科書の最初のページに出てくるこの手続きを、半世紀かけて誰も本質的に超えられていません。

貪欲がlog倍まで悪くなる例 — 集合被覆

集合被覆問題は、いくつかの集合の中から最小個数を選んで全要素を覆う問題です。全業務をカバーする人選、全機能を網羅する最小のテストケース群、といった形で現場に出てきます。

こちらの貪欲は「まだ覆われていない要素を最も多く覆う集合」を毎回選ぶだけ。素直で、実装も10行です。ただし近似比は定数になりません。$H_n = 1 + \tfrac12 + \dots + \tfrac1n \approx \ln n$ 倍まで悪くなる入力が存在します。要素が100万個なら約14倍です。