資料詳細

目次

第Ⅰ部 技法:入門

第1章 近似アルゴリズムへの序論

  1.1 近似アルゴリズムとは?なぜ近似アルゴリズムなのか?

  1.2 技法と線形計画への序論:集合カバー問題

  1.3 確定的ラウンディングアルゴリズム

  1.4 双対解によるラウンディング

  1.5 双対解の構成:主双対法

  1.6 グリーディアルゴリズム

  1.7 乱択ラウンディングアルゴリズム

  1.8 演習問題

  1.9 ノートと発展文献

第2章 グリーディアルゴリズムと局所探索アルゴリズム

  2.1 単一マシーンによる期限付きジョブのスケジューリング

  2.2 k-センター問題

  2.3 同一並列マシーン上でのジョブのスケジューリング

  2.4 巡回セールスマン問題

  2.5 銀行口座の浮動資金の最大化

  2.6 最小次数全点木問題に対する局所探索アルゴリズム

  2.7 辺彩色

  2.8 演習問題

  2.9 ノートと発展文献

第3章 データのラウンディングと動的計画

  3.1 ナップサック問題

  3.2 同一並列マシーン上でのジョブのスケジューリング

  3.3 ビンパッキング問題

  3.4 演習問題

  3.5 ノートと発展文献

第4章 線形計画問題での確定的ラウンディング

  4.1 単一マシーンによるジョブの完了時刻の和の最小化スケジューリング

  4.2 単一マシーンによるジョブの重み付き完了時刻の和の最小化

  4.3 大規模線形計画問題の楕円体法による多項式時間解法

  4.4 賞金獲得シュタイナー木問題

  4.5 容量制約なし施設配置問題

  4.6 ビンパッキング問題

  4.7 演習間題

  4.8 ノートと発展文献

第5章 ランダムサンプリングと線形計画問題での乱択ラウンディング

  5.1 MAX SATとMAX CUTに対する単純なアルゴリズム

  5.2 脱乱択

  5.3 偏りのあるコイン投げ

  5.4 乱択ラウンディング

  5.5 二つの解の良いほうの解を選択する

  5.6 非線形乱択ラウンディング

  5.7 賞金獲得シュタイナー木問題

  5.8 容量制約なし施設配置問題

  5.9 単一マシーンによるジョブの重み付き完了時刻の和の最小化

第6章 半正定値計画問題での乱択ラウンディング

  6.1 半正定値計画の簡単な紹介

  6.2 大きいカットを求める

  6.3 二次計画問題の近似解

  6.4 相関クラスタリングを求める

  6.5 3-彩色可能グラフの彩色

  6.6 演習問題

  6.7 ノートと発展文献

第7章 主双対法

  7.1 集合カバー問題:復習

  7.2 値を増加する変数の選択:無向グラフのフィードバック点集合問題

  7.3 主解の整理:最短s‐tパス問題

  7.4 複数の変数の値の同時増加:一般化シュタイナー木問題

  7.5 不等式の強化:最小ナップサック問題

  7.6 容量制約なし施設配置問題

  7.7 ラグランジュ緩和とk-メディアン問題

  7.8 演習問題

  7.9 ノートと発展文献

第8章 カットとメトリック

  8.1 多分割カット問題と最小カットに基づくアルゴリズム

  8.2 多分割カット問題とLPラウンディングアルゴリズム

  8.3 多点対カット問題

  8.4 平衡カット

  8.5 木メトリックによるメトリックの確率的近似

  8.6 木メトリックの応用:まとめ買いネットワーク設計

  8.7 延伸メトリックと木メトリックと線形アレンジメント

  8.8 演習問題

  8.9 ノートと発展文献

第Ⅱ部 技法:発展

第9章 グリーディアルゴリズムと局所探索アルゴリズムの発展利用

  9.1 容量制約なし施設配置問題に対する局所探索アルゴリズム

  9.2 k-メディアン問題に対する局所探索アルゴリズム

  9.3 最小次数全点木

  9.4 容量制約なし施設配置問題に対するグリーディアルゴリズム

  9.5 演習問題

  9.6 ノートと発展文献

第10章 データのラウンディングと動的計画の発展利用

  10.1 ユークリッド平面上の巡回セールスマン問題

  10.2 平面的グラフの最大独立集合

  10.3 演習問題

  10.4 ノートと発展文献

第11章 線形計画問題での確定的ラウンディングの発展利用

  11.1 一般化割当て問題

  11.2 最小コスト次数上界付き全点木

  11.3 サバイバルネットワーク設計と反復ラウンディング

  11.4 演習問題

  11.5 ノートと発展文献

第12章 ランダムサンプリングとLP乱択ラウンディングの発展利用

  12.1 容量制約なし施設配置問題

  12.2 単一ソースのレンタル・購入問題

  12.3 シュタイナー木問題

  12.4 すべてを同時に解決:デンスグラフの大きいカットの求解

  12.5 演習問題

  12.6 ノートと発展文献

第13章 半正定値計画問題での乱択ラウンディングの発展利用

  13.1 二次計画問題の近似

  13.2 3-彩色可能グラフの彩色

  13.3 ユニークゲーム

  13.4 演習問題

  13.5 ノートと発展文献

第14章 主双対法の発展利用

  14.1 賞金獲得シュタイナー木問題

  14.2 無向グラフのフィードバック点集合問題

  14.3 演習問題

  14.4 ノートと発展文献

第15章 カットとメトリックの発展利用

  15.1 低歪み埋め込みと最疎カット問題

  15.2 需要未確定ルーティングとカット木パッキング

  15.3 カット木パッキングと最小二等分割問題

  15.4 一様最疎カット問題

  15.5 演習問題

  15.6 ノートと発展文献

第16章 近似困難性の証明技法

  16.1 NP-完全問題からのリダクション

  16.2 近似保存リダクション

  16.3 確率的検証可能証明からのリダクション

  16.4 ラベルカバー問題からのリダクション

  16.5 ユニークゲーム問題からのリダクション

  16.6 ノートと発展文献

第17章 未解決問題

付録A 線形計画

付録B NP-完全性

ページの先頭へ