第１章近似アルゴリズムの基礎
- １．１ウォーミングアップ問題
- １．２性能保証付き近似アルゴリズムの基礎概念
- １．３完了時刻最小化スケジューリング
- １．４最小点カバー問題
- １．５巡回セールスマン問題（ＴＳＰ）
- １．６まとめと文献ノート
- １．７演習問題
- １．８発展：近似保証の改善
- １．９発展：近似アルゴリズムの設計と解析の一般的注意
第２章クラスＰＴＡＳ
- ２．１ウォーミングアップ問題
- ２．２最小二分割問題と最小ビンパッキング問題
- ２．３最小二分割問題に対するＰＴＡＳ
- ２．４最小ビンパッキング問題はＰＴＡＳに属さない
- ２．５単純なビンパッキングアルゴリズム：ＮＦ，ＦＦ，ＦＦＤ
- ２．６まとめと文献ノート
- ２．７演習問題
- ２．８発展：完了時刻最小化スケジューリングに対するＰＴＡＳ
- ２．９発展：平面グラフの最大独立集合問題に対するＰＴＡＳ
第３章クラスＦＰＴＡＳ
- ３．１ウォーミングアップ問題
- ３．２ナップサック問題と関連する問題
- ３．３ナップサック問題に対する擬多項式時間アルゴリズム
- ３．４ナップサック問題に対するＦＰＴＡＳ
- ３．５擬多項式時間アルゴリズムとＦＰＴＡＳ
- ３．６まとめと文献ノート
- ３．７演習問題
第４章クラスｌｏｇ‐ＡＰＸとクラスｐｏｌｙ‐ＡＰＸ
- ４．１ウォーミングアップ問題
- ４．２集合カバー問題
- ４．３クラスｐｏｌｙ‐ＡＰＸ
- ４．４まとめと文献ノート
- ４．５演習問題
第５章線形計画と整数計画
- ５．１ウォーミングアップ問題
- ５．２線形計画問題：主問題と双対問題
- ５．３双対定理と相補性条件
- ５．４最適化問題の整数計画問題による定式化
- ５．５まとめと文献ノート
- ５．６演習問題
第６章線形計画による近似アルゴリズムデザイン
- ６．１ウォーミングアップ問題
- ６．２集合カバー問題の整数計画問題としての定式化
- ６．３集合カバー問題に対する確定的ラウンディング
- ６．４近似アルゴリズムにおける主双対法の概観
- ６．５主双対法による集合カバーアルゴリズム
- ６．６双対フィット法による近似保証解析
- ６．７乱択ラウンディング
- ６．８まとめと文献ノート
- ６．９演習問題
第７章施設配置問題
- ７．１ウォーミングアップ問題
- ７．２施設配置問題の定義
- ７．３施設配置問題の整数計画による定式化
- ７．４確定的ラウンディングアルゴリズム
- ７．５乱択ラウンディングアルゴリズム
- ７．６主双対法
- ７．７グリーディアルゴリズム
- ７．８局所探索アルゴリズム
- ７．９まとめと文献ノート
第８章ｋ−センター問題とｋ−メディアン問題
- ８．１ウォーミングアップ問題
- ８．２ｋ−センター問題
- ８．３ラグランジュ緩和とｋ−メディアン問題
- ８．４ｋ−メディアン問題に対する局所探索アルゴリズム
- ８．５まとめと文献ノート
第９章シュタイナー森問題
- ９．１ウォーミングアップ問題
- ９．２シュタイナー木問題
- ９．３ユークリッド空間のシュタイナー木問題
- ９．４ネットワーク版のシュタイナー木問題
- ９．５シュタイナー森問題
- ９．６シュタイナー森問題に対する近似アルゴリズム
- ９．７Ａｇｒａｗａｌ−Ｋｌｅｉｎ−Ｒａｖｉのアルゴリズム
- ９．８その他のアルゴリズム
- ９．９シュタイナー森アルゴリズムの計算機実験
- ９．１０まとめと文献ノート
第１０章最大充足化問題に対する確率的方法
- １０．１ウォーミングアップ問題
- １０．２充足性判定問題と最大充足化問題
- １０．３最大充足化問題に対する確率的方法
- １０．４最大カット問題に対する確率的方法
- １０．５ＭＡＸＳＡＴに対する０．６１８−近似アルゴリズム
- １０．６ＭＡＸＳＡＴに対する線形計画緩和アルゴリズム
- １０．７まとめと文献ノート
第１１章半正定値計画問題での乱択ラウンディング
- １１．１ウォーミングアップ問題
- １１．２半正定値計画の簡単な紹介
- １１．３大きいカットを求める
- １１．４発展：ＭＡＸＳＡＴに対するアルゴリズムの高性能化
- １１．５発展：ＭＡＸＳＡＴに対するＳＤＰ緩和
- １１．６まとめと文献ノート