近似アルゴリズム―離散最適化問題への効果的アプローチ― 

書籍情報
シリーズ名アルゴリズム・サイエンスシリーズ 全16巻 数理技法編 【11】巻
ISBN978-4-320-12177-5
判型A5 
ページ数348ページ
発売予定2019年06月28日
本体価格4,000円
近似アルゴリズム 書影
近似アルゴリズム

新刊

 離散最適化問題は,現実世界で起こる様々な問題を抽象化した最適化問題で,機械学習も含めて多くの分野で注目されている。しかしながら,それらの問題では,高速に最適解を求めることができないことも多く,実際には,高性能の近似解を高速に求めて代用することが多い。このような状況下での近似アルゴリズム理論の研究は,得られる近似解の近似性能を保証するアルゴリズムの研究とも言える。
 そこで,本書では,得られる近似解の近似性能を保証するアルゴリズムについて,わかりやすく解説する。とくに,近似性能の上界を下げるためには,より良い近似性能をもつアルゴリズムを設計し解析しなければならないが,そのための系統的な設計解析法である数理計画に基づくアルゴリズムに焦点を当てて,代表的な問題で具体例を通して,懇切丁寧に解説する。また,近似性能の下界を明らかにするための標準的な技法についても簡単に触れる。さらに,近似性能に応じて問題が分類できることも示す。

目次

第1章 近似アルゴリズムの基礎
1.1 ウォーミングアップ問題
1.2 性能保証付き近似アルゴリズムの基礎概念
1.3 完了時刻最小化スケジューリング
1.4 最小点カバー問題
1.5 巡回セールスマン問題(TSP)
1.6 まとめと文献ノート
1.7 演習問題
1.8 発展:近似保証の改善
1.9 発展:近似アルゴリズムの設計と解析の一般的注意

第2章 クラスPTAS
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 発展:MAX SAT に対するアルゴリズムの高性能化
11.5 発展:MAX SAT に対するSDP 緩和
11.6 まとめと文献ノート

参考文献
索引