近似アルゴリズムの設計

引用

Williamson, D. P., & Shmoys, D. B. (2011). The Design of Approximation Algorithms. Cambridge University Press. 著者による無料の電子版：https://www.designofapproxalgs.com/download.php

章の要約

本書は問題ごとではなくアルゴリズムの技法ごとに構成されている。第1章は一つの問題に複数の技法を適用し、第I部（第1〜8章）は技法ごとに入門の章を一つずつ置き、第II部（第9〜15章）は同じ順序で各技法に戻って、より難しい応用を扱う。第16章、第17章と二つの付録で締めくくられる。各章は演習問題と、文献を示す章末ノートで終わる。

第1章：近似アルゴリズム入門

近似アルゴリズムを学ぶ理由を述べ、性能保証と近似スキームを定義し、良い近似がまったく存在しない問題があることを指摘する。続いて集合被覆問題を五通りに扱う。線形計画の決定的丸め、双対解の丸め、主双対法、貪欲法、確率的丸めである。線形計画の用語はここで導入される。

第2章：貪欲法と局所探索

貪欲法と局所探索を対比する。扱う問題は、単一機械での納期付きスケジューリング、k-センター問題（係数が2未満なら P = NP になるという困難性の結果を含む）、同一並列機械上のスケジューリング、距離空間上の巡回セールスマン問題（最近追加法、二重木、クリストフィデスのアルゴリズム）、銀行口座のフロートの最大化、最小次数全域木、辺彩色である。

第3章：データの丸めと動的計画法

丸めた入力に動的計画法を用いて、ナップサック問題、同一並列機械のスケジューリング、ビンパッキングの近似スキームを得る。

第4章：線形計画の決定的丸め

分数解を決定的に丸める。応用は、単一機械での（重み付き）完了時間和の最小化、賞金収集シュタイナー木問題、容量制約なし施設配置、ビンパッキングである。大規模な線形計画を楕円体法で多項式時間で解く方法を説明する節もある。

第5章：線形計画のランダムサンプリングと確率的丸め

MAX SAT と MAX CUT の単純な乱択アルゴリズムから始め、脱乱択、偏ったコイン、確率的丸めを扱い、続いて非線形の丸めと二つの解のうち良いほうを選ぶ方法を述べる。さらに、賞金収集シュタイナー木、施設配置、解放時刻付きの単一機械スケジューリング、チェルノフ限界、整数多品種流、密な3彩色可能グラフの彩色が扱われる。

第6章：半正定値計画の確率的丸め

半正定値計画と、ランダムな超平面による丸めを導入する。応用は、大きなカットの発見、二次計画の近似、相関クラスタリング、3彩色可能グラフの彩色である。

第7章：主双対法

一連の問題を通して示される原則に沿って、この方法を展開する。集合被覆の復習、帰還頂点集合、最短 s-t パス、一般化シュタイナー木問題、最小ナップサック問題、そしてラグランジュ緩和を用いた容量制約なし施設配置と k-メディアン問題である。

第8章：カットと距離空間

カットの問題を距離空間と線形計画を通して扱う。多方向カット（最小カットに基づくアルゴリズムと線形計画の丸めによるアルゴリズム）、マルチカット、平衡カット、木距離空間による距離空間の確率的近似（応用としてバイ・アット・バルク・ネットワーク設計）、線形配置のための拡散距離空間である。

第9〜10章：貪欲法と局所探索のさらなる応用；データの丸めと動的計画法のさらなる応用

第9章は最小次数全域木の局所探索に戻って最適値との差が1以内の結果を示し、施設配置と k-メディアン問題の局所探索と貪欲法を展開する。第10章は、平面の再帰的な分割に対する動的計画法によるユークリッド巡回セールスマン問題の近似スキームと、平面グラフの最大独立集合の近似スキームを与える。

第11〜12章：線形計画の決定的丸めのさらなる応用；ランダムサンプリングと確率的丸めのさらなる応用

第11章は一般化割当問題、最小費用の次数制約付き全域木、基底実行可能解に基づく反復丸めによる生存可能ネットワーク設計を扱う。第12章は、組み合わせた乱択アルゴリズムで再び施設配置に戻り、続いて単一始点の賃貸か購入かの問題、シュタイナー木問題、密なグラフでの大きなカットの発見を扱う。

第13〜15章：半正定値計画、主双対法、カットと距離空間のさらなる応用

第13章は正規分布の性質を用いて半正定値計画の解析を二次計画と3彩色可能グラフに拡張し、ユニークゲームを加える。第14章は賞金収集シュタイナー木と帰還頂点集合の主双対2近似アルゴリズムを与える。第15章は低歪み埋め込みとスパースカット、オブリビアスルーティング、カット木パッキング、最小二分割、一様スパースカット問題を扱い、最後の節は本書で最も長く複雑な証明である。

第16章：近似困難性を証明する技法

近似困難性の証明を比較的短く概観する。NP 完全問題からの帰着、近似を保つ帰着、確率的検証可能証明からの帰着、ラベルカバーからの帰着、ユニークゲームからの帰着である。

第17章：未解決問題

ユニークゲーム予想から始まる未解決問題の一覧で、距離空間上の巡回セールスマン問題とその非対称版が含まれる。

付録 A〜B：線形計画；NP 完全性

本文が用いる線形計画と計算複雑性の背景の短い復習。

主要概念

第1〜3章：基礎

• 性能保証：多項式時間アルゴリズムが、すべてのインスタンスで最適値の α 倍以内の解を出すとき、α 近似アルゴリズムと呼ぶ。
• 近似スキーム（PTAS）：任意の固定された ε に対して 1±ε を達成するアルゴリズムの族。
• 局所探索と貪欲な構成：局所的に最良の選択で解を作り、あるいは改善すること。

第4〜8章：線形計画、半正定値計画、主双対、距離空間

• 線形計画緩和と丸め：整数計画の分数版を解き、整数解に変換すること。
• 確率的丸めと脱乱択：ランダムな選択を期待値で解析し、条件付き期待値法で除去すること。
• 主双対法：主解と並行して実行可能な双対解を構成し、コストを抑えること。
• 木距離空間：一般の距離空間を、対数程度の損失でランダムな木によって近似すること。

第9〜17章：拡張と限界

• 反復丸め：線形計画を繰り返し解いて変数を固定する方法で、次数制約付きや生存可能ネットワーク設計に用いる。
• 整数性ギャップ：整数計画とその緩和の差で、ある定式化で証明できることを制限する。
• 近似を保つ帰着とユニークゲーム予想：困難性の結果を示す道具。

批判的分析

長所

• 技法を軸にした構成。 技法ごとに章があるため、丸め、主双対、局所探索のどれをいつ使うかが学べる。施設配置、賞金収集シュタイナー木、ビンパッキング、最大カットに繰り返し戻ることで、より良い道具が結果を改善する様子が示される。
• 線形計画による統一的な視点。 序文は線形計画と整数計画を中心に据えると述べており、第1章と付録 A が計算機科学出身の読者に用語を補う。
• 教育を意識した設計。 本文は何度も行われた講義から生まれ、授業で扱える程度に単純な結果に限られ、各章末には演習とノートが付く。
• 困難性に率直。 困難性は第1章と第2章ですでに現れ、第16章と未解決問題の章が、何が改善できないかを説明する。

短所

• 前提知識は実際に必要。 序文は、アルゴリズムの講義の受講経験、証明に慣れていること、基本的な確率、NP 完全性の多少の知識を前提としており、半正定値計画には基礎的な線形代数も必要である。序文によれば、本文中の少数の NP 完全性の帰着は読み飛ばしてよい。
• 困難性の扱いは概観のみ。 著者は、この主題だけで別の本が書けると述べており、第16章は短い。
• 一部の内容は古い。 未解決問題の章は2010年時点の状況を反映し、発表されていない成果の発表予定にも触れている。
• 第II部は密度が高い。 第II部は入門ではない。序文の言葉では、第15章の Arora–Rao–Vazirani の証明は本書で最も長く複雑である。

コースにおける位置づけ

アルゴリズムのコースの中で、本書は Introduction to Algorithms のような一般的なアルゴリズムの教科書の次に読む大学院向けの専門書である。最も近い代替は Vazirani の Approximation Algorithms で、これも NP 困難問題の技法を詳しく扱う。Williamson と Shmoys は技法ごとに構成して同じ問題に繰り返し戻り、著者自身の説明では、スケジューリングと半正定値計画により多くを割いている。

Mitzenmacher と Upfal の Probability and Computing は、確率に関する章（第5、6、12、13章）の補助として役立つ。チェルノフ限界と確率的方法を深く展開しているからである。The Algorithm Design Manual、Algorithms Illuminated、Algorithms Unlocked のような応用寄りの本は設計と実装を扱うもので、本書の代わりにはならない。

本書の使い方

本書は、近似アルゴリズムを始める大学院生と研究者を対象としている。最初は第I部を順に読むとよい。第1章が集合被覆で全体像を示し、第2章と第3章はアルゴリズムの知識以上はほとんど必要とせず、第4、5、7章が線形計画に基づく方法を展開する。第6章は線形代数を必要とし、第8章は線形計画と距離空間の考え方を組み合わせる。

第I部のある技法を読んだ後でより強い結果を見たいときは、第II部の対応する章に進む。第9章と第11.1節が最初の手がかりとして適しており、第16章が困難性の背景を与える。各章で少なくとも数問は演習を解き、章末ノートで原論文を探すとよい。

版と出典

この導読は、著者のウェブサイトで公開されている無料の電子版（電子版のみ）に基づく。ケンブリッジ大学出版局の許可を得て公開されたこのファイルは、出版社に提出された原稿で、印刷版とは書式が異なり、小さな訂正がある。序文、目次、各章の冒頭、末尾の章と付録を踏まえている。