近似アルゴリズム

引用

Vazirani, V. V. (2001). Approximation Algorithms (1st ed.). Springer. (Corrected second printing 2003; softcover reprint 2010.)

章の要約

本書は三部構成で全30章、付録が二つある。ほとんどの章が一つの問題を軸にし、章末に演習と注記が付き、本文は短くまとめられている。

第1章：Introduction（序論）

近似保証の基本的な考え方を示し、頂点被覆を例に、最適値（OPT）の下界を求めることが解析の鍵になることを説明する。保証を改善できるかという問い、良特徴づけ問題（well-characterized problems）、min-max関係も導入される。

第I部 第2〜4章：集合被覆、シュタイナー木とTSP、多端子カットとk-カット

集合被覆は貪欲法と層別化（layering）で扱われ、最短共通超文字列への応用が付く。続いてシュタイナー木と距離空間上のTSPが取り上げられ、単純な2近似と3/2への改善が示される。その後に多端子カットと最小k-カットが続く。

第I部 第5〜7章：k-センター、フィードバック頂点集合、最短共通超文字列

k-センターはパラメトリック枝刈りで扱われ、重み付き版も含む。フィードバック頂点集合では巡回数（cyclomatic）重み付きグラフと層別化を用いる。最短共通超文字列では4近似の後、3近似への改善が示される。

第I部 第8〜11章：ナップサック、ビンパッキング、最小メイクスパン・スケジューリング、ユークリッドTSP

これらの章は近似スキームが中心である。ナップサックには擬多項式時間アルゴリズム、FPTAS、強NP困難性の議論がある。ビンパッキングでは漸近的PTAS、メイクスパン・スケジューリングでは2近似とPTASが、ユークリッドTSPではアルゴリズムとその正当性の証明が示される。

第II部 第12〜15章：LP双対性と集合被覆

第12章はLP双対性、min-max関係、この部の二つの設計技法（丸めと主双対法）、整数性ギャップを導入する。第13〜15章は集合被覆に三度戻り、貪欲法の双対フィッティングによる解析、丸め（単純な丸めと確率的丸め、頂点被覆の半整数性）、主双対法を扱う。

第II部 第16〜21章：最大充足可能性から最疎カットまで

最大充足可能性は脱乱択化とLP丸めで扱われ、3/4近似に至る。関連のない並列機械上のスケジューリングでは端点解の性質を使う。第18〜21章は、木上のマルチカット、多端子カット、一般グラフのマルチカット、最疎カットを扱い、最後のものは計量、カット詰め込み、低歪み埋め込みを用いる。

第II部 第22〜26章：シュタイナー森から半正定値計画まで

シュタイナー森は同期付きの主双対法を、シュタイナー・ネットワークは反復丸めを用いる。続いて施設配置とk-メディアンが扱われ、後者にはラグランジュ緩和の技法が含まれる。第26章は半正定値計画を導入し、MAX-2SATに確率的丸めを適用する。

第III部 第27〜30章：その他の話題

格子の最短ベクトル（第27章）、二つの数え上げ問題（DNFの解の数とネットワーク信頼性、第28章）、PCP定理に基づく近似困難性と集合被覆の困難性結果（第29章）、未解決問題の一覧（第30章）である。付録Aはアルゴリズム設計者向けの計算量理論の概観、付録Bは基本的な確率論である。

主要概念

第1〜11章

• OPTの下界：近似比の証明は、アルゴリズムの出力を、容易に計算できる最適値の下界と比べることで行われる。
• 層別化とパラメトリック枝刈り：集合被覆、フィードバック頂点集合、k-センターに使われる二つの組合せ的技法。
• PTASとFPTAS：保証を1に限りなく近づけられるスキーム。ナップサックの章では、FPTASがそもそも存在しうるのはいつかが問われる。

第12〜26章

• LP双対性と整数性ギャップ：線形計画とその双対を結ぶ定理と、ある緩和に基づく解析の限界を与える比。
• 双対フィッティング、丸め、主双対法：LP緩和から保証付きアルゴリズムを作る三つの方法。
• 反復丸めと半正定値緩和：シュタイナー・ネットワークやMAX-2SATに用いられる、より精巧な丸め法。

第27〜30章

• ギャップ帰着とPCP定理：近似困難性の結果を支える道具立て。
• 近似的数え上げ：解を最適化するのではなく、解の個数を近似すること。

批判的分析

長所

• 一つの問題を軸にした短い章。 序文によれば、各章は短く単純に保たれ、しばしば鍵となる結果だけを示し、一般化は演習に回されている。一章ずつ読み進めやすい。
• 演習とヒント。 ほぼすべての章に演習と注記があり、序文によれば一部の演習にはヒントが付く。
• 構成に技法が表れている。 第II部は技法ごとに整理され、集合被覆は貪欲法、双対フィッティング、丸め、主双対法で再訪された後、第29章で対応する困難性結果が示される。一つの問題を複数の角度から見られることは教育上有益である。
• 背景知識が本書内で完結している。 付録で計算量理論と確率を扱い、LP、半正定値計画、格子はそれぞれ第12、26、27章で導入される。
• 書評の評価。 Mark Jerrum（Mathematical Reviews, 2002）は、この主題を広く体系的に扱った最初の教科書かもしれないと述べ、豊富な演習を称賛した。Viggo Kann（Zentralblatt MATH, 2003）は結果が元の論文より理解しやすいことが多いとし、Csanád Imreh（Acta Scientiarum Mathematicarum, 2002）は大学院の講義にも研究者にも使えると評した。

短所

• 2001年時点のスナップショット。 著者は、本書が執筆時点の理論を示すものであり、状況は変わるだろうと書いている。未解決問題の一覧も当時流行の問題を中心にしたものと説明されている。
• 第I部は意図的に多様。 序文は、技法を厳密に分類しなかったため、組合せ的アルゴリズムの部が非凝集的に見えるかもしれないと認めている。技法順の講義を望む読者には第II部のほうが体系的に感じられる。
• 一部の証明は受け入れる必要がある。 第29章はPCP定理を前提とし、序文によればその単純な証明は存在しない。数え上げのためのマルコフ連鎖モンテカルロ法も扱われない。
• 一つの講義を超える分量。 序文によれば、半期の講義の2倍を超える内容があるため、読者は自分で道筋を選ぶ必要がある。

コースにおける位置づけ

このコースの書籍リストの中で、Vaziraniは専門的な教科書である。Introduction to Algorithms（Cormen、Leiserson、Rivest、Stein）は汎用の参考書で、第35章が近似アルゴリズム、第34章がNP完全性を扱い、後者はVaziraniが前提とする内容である。SkienaのThe Algorithm Design Manualは、アルゴリズム上の問題を見分けて解くための実践的な手引きで、近似もその手法の一つである。RoughgardenのAlgorithms IlluminatedとCormenのAlgorithms Unlockedは、大学院向けの教科書にまだ進めない読者のための、より穏やかなアルゴリズム入門である。

最も近い比較対象は、同じ主題の大学院向け教科書であるWilliamsonとShmoysのThe Design of Approximation Algorithmsで、そのページの紹介では貪欲法から半正定値計画までを扱い、理論的限界も論じるとされている。両書とも中心部分を扱うが、Vaziraniは問題中心の短い章と三部構成が特徴で、並べて読むのに向く。Mitzenmacherらの Probability and Computing は、第14、16、26章の確率的丸めの補助として役立つ。

本書の使い方

本書は高学年の学部生と大学院生向けである。序文は、学部のアルゴリズム講義とNP完全性の理論があれば大半の章に十分だとし、付録AとBで計算量と確率を復習できる。

最初の読み方としては、第1章、続いて第I部の第2、3、5、8〜10章がよい（序文によれば各部の章はおおよそ難しくなる順に並ぶ）。次に第12〜15章で、一つの身近な問題を通してLP双対性と三つのLP技法を学び、その後に第16、17、24章へ進む。第18〜23、25、26章は、カット、ネットワーク設計、クラスタリング、半正定値の手法を学びたい読者のための任意の二周目である。困難性の側面に関心がある読者は、付録Aの後に第29章を読むとよい。一般的なアルゴリズムの講義については、序文は第I部・第II部の最初の数章を補助教材として勧めているにすぎない。

演習に取り組むこと。一般化や関連する結果は演習に置かれ、章末の注記が更なる文献を示している。