| タイトルコード |
1000100724185 |
| 書誌種別 |
図書 |
| 書名 |
近似アルゴリズム |
| 書名ヨミ |
キンジ アルゴリズム |
|
離散最適化問題への効果的アプローチ |
| 叢書名 |
アルゴリズム・サイエンスシリーズ
|
| 叢書番号 |
11 |
| 言語区分 |
日本語 |
| 著者名 |
浅野 孝夫／著
|
| 著者名ヨミ |
アサノ タカオ |
| 出版地 |
東京 |
| 出版者 |
共立出版
|
| 出版年月 |
2019.6 |
| 本体価格 |
￥４０００ |
| ISBN |
978-4-320-12177-5 |
| ISBN |
4-320-12177-5 |
| 数量 |
12,333p |
| 大きさ |
22cm |
| 分類記号 |
007.64
|
| 件名 |
アルゴリズム
最適化
|
| 注記 |
文献:p319〜328 |
| 内容紹介 |
離散最適化問題の最適解に近い解を多項式時間で求める近似アルゴリズムのテキスト。近似性能保証付きアルゴリズムの基礎概念を例題と図を用いて解説した上で、その系統的なデザインと解析の技法を説明する。 |
| 著者紹介 |
1949年生まれ。東北大学大学院工学研究科電気・通信工学専攻博士課程修了。中央大学名誉教授。専門は情報工学、離散アルゴリズム。著書に「グラフ・ネットワークアルゴリズムの基礎」など。 |
| 目次タイトル |
第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 まとめと文献ノート |
