第1章 はじめに 1 |
1.1 列挙 2 |
1.2 アルゴリズムの計算時間 6 |
1.3 線形の最適化問題 9 |
1.4 ソーティング 11 |
演習問題 13 |
参考文献 14 |
第2章 グラフ 15 |
2.1 基礎的な定義 15 |
2.2 木,閉路,カット 20 |
2.3 連結性 28 |
2.4 オイラーグラフと2部グラフ 35 |
2.5 平面性 38 |
2.6 平面的双対性 46 |
演習問題 48 |
参考文献 52 |
第3章 線形計画法 54 |
3.1 多面体 55 |
3.2 単体法 61 |
3.3 双対性 66 |
3.4 凸包と有界多面体 70 |
演習問題 72 |
参考文献 74 |
第4章 線形計画とアルゴリズム 76 |
4.1 頂点と面のサイズ 76 |
4.2 連分数 80 |
4.3 ガウスの消去法 83 |
4.4 楕円体法 88 |
4.5 Khachiyanの定理 94 |
4.6 分離問題と最適化 96 |
演習問題 103 |
参考文献 105 |
第5章 整数計画法 106 |
5.1 多面体の整数包 107 |
5.2 ユニモジュラー変換 112 |
5.3 完全双対整数性 114 |
5.4 完全ユニモジュラー行列 119 |
5.5 切除平面法 125 |
5.6 ラグランジュ緩和 130 |
演習問題 132 |
参考文献 135 |
第6章 全点木と有向木 138 |
6.1 最小全点木問題 139 |
6.2 最小重み有向木 145 |
6.3 多面体的表現 149 |
6.4 全点木と有向木のパッキング 152 |
演習問題 156 |
参考文献 160 |
第7章 最短パス 163 |
7.1 1点からの最短パス 164 |
7.2 全点間の最短パス 169 |
7.3 最小平均長閉路 172 |
演習問題 174 |
参考文献 176 |
第8章 ネットワークフロー 179 |
8.1 最大フロー最小カット定理 180 |
8.2 Mengerの定理 184 |
8.3 Edmonds-Karpアルゴリズム 186 |
8.4 ブロックフローと藤重(Fujishige)のアルゴリズム 188 |
8.5 Goldberg-Tarjanアルゴリズム 191 |
8.6 Gomory-Hu木 196 |
8.7 無向グラフの最小カット 202 |
演習問題 205 |
参考文献 210 |
第9章 最小費用フロー 214 |
9.1 問題の定式化 214 |
9.2 最適性基準 216 |
9.3 最小平均長閉路解消アルゴリズム 219 |
9.4 最短パス反復アルゴリズム 222 |
9.5 Orlinのアルゴリズム 226 |
9.6 時変フロー 231 |
演習問題 333 |
参考文献 237 |
第10章 最大マッチング 239 |
10.1 2部グラフのマッチング 240 |
10.2 Tutte行列 242 |
10.3 Tutteの定理 244 |
10.4 因子臨界的グラフの耳分解 247 |
10.5 Edmondsのマッチングアルゴリズム 253 |
演習問題 263 |
参考文献 267 |
第11章 重み付きマッチング 270 |
11.1 割当問題 271 |
11.2 重み付きマッチングアルゴリズムの概略 272 |
11.3 重み付きマッチングアルゴリズムの実装 275 |
11.4 事後最適性 289 |
11.5 マッチング多面体 291 |
演習問題 294 |
参考文献 296 |
第12章 b-マッチングとT-ジョイン 298 |
12.1 b-マッチング 298 |
12.2 最小重みT-ジョイン 303 |
12.3 T-ジョインとT-カット 307 |
12.4 Padberg-Raoの定理 310 |
演習問題 314 |
参考文献 317 |
第13章 マトロイド 319 |
13.1 独立性システムとマドロイド 319 |
13.2 他のマトロイド公理系 324 |
13.3 双対性 329 |
13.4 グリーディ法 333 |
13.5 マトロイドの共通独立集合 338 |
13.6 マトロイド分割 343 |
13.7 重み付きマトロイド交差 345 |
演習問題 349 |
参考文献 351 |
第14章 マトロイドの一般化 354 |
14.1 グリードイド 354 |
14.2 ポリマトロイド 358 |
14.3 劣モジュラー関数の最小化 363 |
14.4 Schrijverのアルゴリズム 366 |
14.5 対称劣モジュラー関数 371 |
演習問題 373 |
参考文献 376 |
第15章 NP-完全性 378 |
15.1 チューリング機械 379 |
15.2 Churchの提唱 381 |
15.3 PとNP 386 |
15.4 Cookの定理 391 |
15.5 いくつかの基本的なNP-完全問題 395 |
15.6 クラスcoNP 403 |
15.7 NP-困難問題 404 |
演習問題 409 |
参考文献 412 |
第16章 近似アルゴリズム 414 |
16.1 集合カバー 415 |
16.2 彩色 420 |
16.3 近似スキーム 428 |
16.4 最大充足化問題 430 |
16.5 PCP定理 436 |
16.6 L-帰着 440 |
演習問題 447 |
参考文献 450 |
第17章 ナップサック問題 455 |
17.1 小数ナップサック問題と重み付き中央値問題 455 |
17.2 擬似多項式時間アルゴリズム 458 |
17.3 完全多項式近似スキーム 460 |
演習問題 463 |
参考文献 464 |
第18章 ビンパッキング問題 466 |
18.1 グリーディ法 467 |
18.2 漸近的近似スキーム 472 |
18.3 Karmarkar-Karpアルゴリズム 476 |
演習問題 480 |
参考文献 481 |
第19章 多品種フローと辺素パス 484 |
19.1 多品種フロー 485 |
19.2 多品種フローのアルゴリズム 488 |
19.3 有向辺素パス問題 493 |
19.4 無向辺素パス問題 497 |
演習問題 503 |
参考文献 505 |
第20章 ネットワーク設計問題 509 |
20.1 シュタイナー木 510 |
20.2 Robins-Zelikovskyアルゴリズム 515 |
20.3 サバイバルネットワーク設計 521 |
20.4 主双対近似アルゴリズム 524 |
20.5 Jainのアルゴリズム 533 |
演習問題 539 |
参考文献 542 |
第21章 巡回セールスマン問題 546 |
21.1 TSPの近似アルゴリズム 546 |
21.2 ユークリッドTSP 552 |
21.3 場所探索 561 |
21.4 巡回セールスマン多面体 568 |
21.5 下界 575 |
21.6 分枝限定法 577 |
演習問題 580 |
参考文献 582 |
第22章 施設配置問題 586 |
22.1 容量制約なし施設配置問題 586 |
22.2 線形計画問題の解のラウンディング 588 |
22.3 主双対アルゴリズム 590 |
22.4 スケール変換とグリーディ増加操作 597 |
22.5 開設施設数の制約 601 |
22.6 局所探索 605 |
22.7 容量制限付き施設配置問題 611 |
22.8 普遍的施設配置問題 614 |
演習問題 623 |
参考文献 625 |
訳者あとがき 628 |
引用文献著者索引 631 |
問題・アルゴリズム索引 639 |
事項索引 646 |