| タイトルコード |
1000100317279 |
| 書誌種別 |
図書 |
| 書名 |
近似アルゴリズムデザイン |
| 書名ヨミ |
キンジ アルゴリズム デザイン |
| 言語区分 |
日本語 |
| 著者名 |
David P.Williamson／著
David B.Shmoys／著
浅野 孝夫／訳
|
| 著者名ヨミ |
David P Williamson David B Shmoys アサノ タカオ |
| 著者名原綴 |
Williamson David P. Shmoys David B. |
| 出版地 |
東京 |
| 出版者 |
共立出版
|
| 出版年月 |
2015.9 |
| 本体価格 |
￥１２０００ |
| ISBN |
978-4-320-12391-5 |
| ISBN |
4-320-12391-5 |
| 数量 |
13,591p |
| 大きさ |
27cm |
| 分類記号 |
007.64
|
| 件名 |
アルゴリズム
最適化
|
| 注記 |
原タイトル:The design of approximation algorithms |
| 注記 |
文献:p521〜536 |
| 内容紹介 |
近似アルゴリズムの最先端の研究者によるテキスト。近似アルゴリズムデザインの技法とアイデアを、単純な問題を例にとってわかりやすく解説するとともに、より高度な問題に適用する際の工夫を具体的に説明する。 |
| 目次タイトル |
第Ⅰ部 技法:入門 |
|
第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 単一マシーンによるジョブの重み付き完了時刻の和の最小化 5.10 Chernoff限界 5.11 整数多品種フロー 5.12 ランダムサンプリングと3-彩色可能デンスグラフの彩色 5.13 演習問題 5.14 ノートと発展文献 |
|
第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-完全性 |
