出版書誌データベース

　本書は，近似アルゴリズムデザインの技法とアイデアを系統的かつ明快に解説している。　第1部では，単純な問題を例にとり，これらの技法とアイデアを具体的にわかりやすく解説している。第2部では，これらの技法とアイデアを実際のケースで生じるより高度な問題に適用する際の工夫を具体的に解説している。
　本書において系統的な解説を可能にしているのが，線形計画法と整数計画法である。欧米の大学では，本当に実用的なアルゴリズムの研究開発には，これらの分野が極めて重要であることが認識されてきている。したがって，情報科学系でもこれらを講義で取り上げる大学が増加してきていて，本書もそれに後押しされて，その重要性を増してきている。すなわち，これからのアルゴリズム教育には，線形計画法と整数計画法の概念の理解とそれを応用する能力の育成が必要不可欠となると思われるが，本書はそれらも自然に身につくように記述されている。
(David P. Williamson, David B. Shmoys:The Design of Approximation Algorithms, Cambridge University Press, 2011)

第I部　技法：入門

第1章　近似アルゴリズムへの序論
1.1　近似アルゴリズムとは？　なぜ近似アルゴリズムなのか？
1.2　技法と線形計画への序論：集合カバー問題
1.3　確定的ラウンディングアルゴリズム
1.4　双対解によるラウンディング
1.5　双対解の構成：主双対法
1.6　グリーディアルゴリズム
1.7　乱択ラウンディングアルゴリズム

第2章　グリーディアルゴリズムと局所探索アルゴリズム
2.1　単一マシーンによる期限付きジョブのスケジューリング
2.2　k-センター問題
2.3　同一並列マシーン上でのジョブのスケジューリング
2.4　巡回セールスマン問題
2.5　銀行口座の浮動資金の最大化
2.6　最小次数全点木問題に対する局所探索アルゴリズム
2.7　辺彩色

第3章　データのラウンディングと動的計画
3.1　ナップサック問題
3.2　同一並列マシーン上でのジョブのスケジューリング
3.3　ビンパッキング問題

第4章　線形計画問題での確定的ラウンディング
4.1　単一マシーンによるジョブの完了時刻の和の最小化スケジューリング
4.2　単一マシーンによるジョブの重み付き完了時刻の和の最小化
4.3　大規模線形計画問題の楕円体法による多項式時間解法
4.4　賞金獲得シュタイナー木問題
4.5　容量制約なし施設配置問題
4.6　ビンパッキング問題

第5章　ランダムサンプリングと線形計画問題での乱択ラウンディング
5.1　MAXSATとMAXCUTに対する単純なアルゴリズム
5.2　脱乱択
5.3　偏りのあるコイン投げ
5.4　乱択ラウンディング
5.5　二つの解の良いほうの解を選択する
5.6　非線形乱択ラウンディング
5.7　賞金獲得シュタイナー木問題
5.8　容量制約なし施設配置問題
5.9　単一マシーンによるジョブの重み付き完了時刻の和の最小化
5.10　Chernoff限界
5.11　整数多品種フロー
5.12　ランダムサンプリングと3-彩色可能デンスグラフの彩色

第6章　半正定値計画問題での乱択ラウンディング
6.1　半正定値計画の簡単な紹介
6.2　大きいカットを求める
6.3　二次計画問題の近似解
6.4　相関クラスタリングを求める
6.5　3-彩色可能グラフの彩色

第7章　主双対法
7.1　集合カバー問題：復習
7.2　値を増加する変数の選択：無向グラフのフィードバック点集合問題
7.3　主解の整理：最短s-tパス問題
7.4　複数の変数の値の同時増加：一般化シュタイナー木問題
7.5　不等式の強化：最小ナップサック問題
7.6　容量制約なし施設配置問題
7.7　ラグランジュ緩和とk-メジアン問題

第8章　カットとメトリック
8.1　多分割カット問題と最小カットに基づくアルゴリズム
8.2　多分割カット問題とLPラウンディングアルゴリズム
8.3　多点対カット問題
8.4　平衡カット
8.5　木メトリックによるメトリックの確率的近似
8.6　木メトリックの応用：まとめ買いネットワーク設計
8.7　メトリックの延伸と木メトリックと線形アレンジメント


第II部　技法：発展

第9章　グリーディアルゴリズムと局所探索アルゴリズムの発展利用
9.1　容量制約なし施設配置問題に対する局所探索アルゴリズム
9.2　k-メディアン問題に対する局所探索アルゴリズム
9.3　最小次数全点木
9.4　容量制約なし施設配置問題に対するグリーディアルゴリズム

第10章　データのラウンディングと動的計画の発展利用
10.1　ユークリッド平面上の巡回セールスマン問題
10.2　平面的グラフの最大独立集合

第11章　線形計画問題での確定的ラウンディングの発展利用
11.1　一般化割当て問題
11.2　最小コスト次数上界付き全点木
11.3　サバイバルネットワーク設計と反復ラウンディング

第12章　ランダムサンプリングと乱択ラウンディングの発展利用
12.1　容量制約なし施設配置問題
12.2　単一ソースのレンタル・購入問題
12.3　シュタイナー木問題
12.4　すべてを同時に解決：デンスグラフの大きいカットの求解

第13章　半正定値計画問題での乱択ラウンディングの発展利用
13.1　二次計画問題の近似
13.2　3-彩色可能グラフの彩色
13.3　ユニークゲーム

第14章　主双対法の発展利用
14.1　賞金獲得シュタイナー木問題
14.2　無向グラフのフィードバック点集合問題

第15章　カットとメトリックの発展利用
15.1　低歪み埋め込みと最疎カット問題
15.2　需要未確定ルーティングとカット木パッキング
15.3　カット木パッキングと最小二等分割問題
15.4　一様最疎カット問題

第16章　近似困難性の証明技法
16.1　近似保存リダクション
16.2　確率的検証可能証明からのリダクション
16.3　ラベルカバー問題からのリダクション
16.4　ユニークゲーム問題からのリダクション

第17章　未解決問題

付録A　線形計画
付録B　NP-完全性