内容

目次

第1章　近似アルゴリズムの基礎1 1.1 ウォーミングアップ問題 1.2 ウォーミングアップ問題の解説 1.3 性能保証付き近似アルゴリズムの基礎概念 1.4 完了時刻最小化スケジューリング 1.5 最小点カバー問題 1.6 巡回セールスマン問題(TSP) 1.7 まとめと文献ノート 1.8 演習問題 1.9 発展：近似保証の改善 1.10 発展：近似アルゴリズムの設計と解析の一般的注意 第2章　クラスPTAS 33 2.1 ウォーミングアップ問題 2.2 最小二分割問題と最小ビンパッキング問題 2.3 最小二分割問題に対するPTAS 2.4 最小ビンパッキング問題はPTAS に属さない 2.5 単純なビンパッキングアルゴリズム：NF, FF, FFD 2.6 まとめと文献ノート 2.7 演習問題 2.8 発展：完了時刻最小化スケジューリングに対するPTAS 2.9 発展：平面グラフの最大独立集合問題に対するPTAS 第3章　クラスFPTAS 3.1 ウォーミングアップ問題 3.2 ナップサック問題と関連する問題 3.3 ナップサック問題に対する擬多項式時間アルゴリズム 3.4 ナップサック問題に対するFPTAS 3.5 擬多項式時間アルゴリズムとFPTAS 3.6 まとめと文献ノート 3.7 演習問題 第4章　クラスlog-APX とクラスpoly-APX 4.1 ウォーミングアップ問題 4.2 集合カバー問題 4.3 クラスpoly-APX 4.4 まとめと文献ノート 4.5 演習問題 第5章　線形計画と整数計画 5.1 ウォーミングアップ問題 5.2 線形計画問題：主問題と双対問題 5.3 双対定理と相補性条件 5.4 最適化問題の整数計画問題による定式化 5.5 まとめと文献ノート 5.6 演習問題 第6章　線形計画による近似アルゴリズムデザイン 6.1 ウォーミングアップ問題 6.2 集合カバー問題の整数計画問題としての定式化 6.3 集合カバー問題に対する確定的ラウンディング 6.4 近似アルゴリズムにおける主双対法の概観 6.5 主双対法による集合カバーアルゴリズム 6.6 双対フィット法による近似保証解析 6.7 乱択ラウンディング 6.8 まとめと文献ノート 6.9 演習問題 第7章　施設配置問題 7.1 ウォーミングアップ問題 7.2 施設配置問題の定義 7.3 施設配置問題の整数計画による定式化 7.4 確定的ラウンディングアルゴリズム 7.5 乱択ラウンディングアルゴリズム 7.6 主双対法 7.7 グリーディアルゴリズム 7.8 局所探索アルゴリズム 7.9 まとめと文献ノート 第8章　k-センター問題とk-メディアン問題 8.1 ウォーミングアップ問題 8.2 k-センター問題 8.3 ラグランジュ緩和とk-メディアン問題 8.4 k-メディアン問題に対する局所探索アルゴリズム 8.5 まとめと文献ノート 第9章　シュタイナー森問題 9.1 ウォーミングアップ問題 9.2 シュタイナー木問題 9.3 ユークリッド空間のシュタイナー木問題 9.4 ネットワーク版のシュタイナー木問題 9.5 シュタイナー森問題 9.6 シュタイナー森問題に対する近似アルゴリズム 9.7 Agrawal-Klein-Ravi のアルゴリズム 9.8 その他のアルゴリズム 9.9 シュタイナー森アルゴリズムの計算機実験 9.10 まとめと文献ノート 第10章　最大充足化問題に対する確率的方法 10.1 ウォーミングアップ問題 10.2 充足性判定問題と最大充足化問題 10.3 最大充足化問題に対する確率的方法 10.4 最大カット問題に対する確率的方法 10.5 MAX SAT に対する0.618-近似アルゴリズム 10.6 MAX SAT に対する線形計画緩和アルゴリズム 10.7 まとめと文献ノート 第11章　半正定値計画問題での乱択ラウンディング 11.1 ウォーミングアップ問題 11.2 ウォーミングアップ問題の解説 11.3 半正定値計画の簡単な紹介 11.4 大きいカットを求める 11.5 発展：MAX SAT に対するアルゴリズムの高性能化 11.6 発展：MAX SAT に対するSDP 緩和 11.7 まとめと文献ノート 参考文献 索引