記法一覧 ix |
問題一覧 xii |
アルゴリズム一覧 xiv |
第1章 はじめに 1 |
1.1 列挙 2 |
1.2 アルゴリズムの計算時間 6 |
1.3 線形の最適化問題 9 |
1.4 ソーティング 11 |
演習問題 13 |
参考文献 14 |
第2章 グラフ 15 |
2.1 基礎的な定義 15 |
2.2 木,閉路,カット 21 |
2.3 連結性 30 |
2.4 オイラーグラフと2部グラフ 37 |
2.5 平面性 41 |
2.6 平面的双対性 49 |
演習問題 52 |
参考文献 55 |
第3章 線形計画法 58 |
3.1 多面体 61 |
3.2 単体法 68 |
3.3 単体法の実装 72 |
3.4 双対性 76 |
3.5 凸包と有界多面体 80 |
演習問題 83 |
参考文献 85 |
第4章 線形計画アルゴリズム 87 |
4.1 頂点と面のサイズ 87 |
4.2 連分数 91 |
4.3 ガウスの消去法 95 |
4.4 楕円体法 100 |
4.5 Khachiyanの定理 106 |
4.6 分離問題と最適化 109 |
演習問題 116 |
参考文献 118 |
第5章 整数計画法 120 |
5.1 多面体の整数包 123 |
5.2 ユニモジュラー変換 128 |
5.3 完全双対整数性 131 |
5.4 完全ユニモジュラー行列 135 |
5.5 切除平面法 141 |
5.6 ラグランジュ緩和 147 |
演習問題 149 |
参考文献 152 |
第6章 全点木と有向木 155 |
6.1 最小全点木問題 156 |
6.2 最小重み有向木 163 |
6.3 多面体的表現 167 |
6.4 全点木と有向木のパッキング 171 |
演習問題 175 |
参考文献 178 |
第7章 最短パス 182 |
7.1 1点からの最短パス 183 |
7.2 全点間の最短パス 188 |
7.3 最小平均長閉路 191 |
演習問題 194 |
参考文献 195 |
第8章 ネットワークフロー 198 |
8.1 最大フロー最小カット定理 199 |
8.2 Mengerの定理 203 |
8.3 Edmonds-Karpアルゴリズム 206 |
8.4 ブロックフローと藤重(Fujishige)のアルゴリズム 208 |
8.5 Goldberg-Tarjanアルゴリズム 210 |
8.6 Gomory-Hu木 215 |
8.7 無向グラフの最小容量カット 222 |
演習問題 224 |
参考文献 230 |
第9章 最小費用フロー 234 |
9.1 問題の定式化 234 |
9.2 最適性基準 236 |
9.3 最小平均長閉路解消アルゴリズム 239 |
9.4 最短パス反復アルゴリズム 242 |
9.5 Orlinのアルゴリズム 247 |
9.6 ネットワーク単体法 252 |
9.7 時変フロ- 257 |
演習問題 259 |
参考文献 263 |
第10章 最大マッチング 266 |
10.1 2部グラフのマッチング 267 |
10.2 Tutte行列 269 |
10.3 Tutteの定理 272 |
10.4 因子臨界的グラフの耳分解 275 |
10.5 Edmondsのマッチングアルゴリズム 281 |
演習問題 291 |
参考文献 295 |
第11章 重み付きマッチング 299 |
11.1 割当問題 300 |
11.2 重み付きマッチングアルゴリズムの概略 301 |
11.3 重み付きマッチングアルゴリズムの実装 304 |
11.4 事後最適性 318 |
11.5 マッチング多面体 319 |
演習問題 323 |
参考文献 325 |
第12章 b-マッチングとT-ジョイン 327 |
12.1 b-マッチング 327 |
12.2 最小重みT-ジョイン 332 |
12.3 T-ジョインとT-カット 337 |
12.4 Padberg-Raoの定理 341、 |
演習問題 344 |
参考文献 347 |
第13章 マトロイド 349 |
13.1 独立性システムとマトロイド 349 |
13.2 他のマトロイド公理系 354 |
13.3 双対性 359 |
13.4 グリーディ法 363 |
13.5 マトロイドの共通独立集合 369 |
13.6 マトロイド分割 374 |
13.7 重み付きマトロイド交差 376 |
演習問題 380 |
参考文献 383 |
第14章 マトロイドの一般化 385 |
14.1 グリードイド 385 |
14.2 ポリマトロイド 390 |
14.3 劣モジュラー関数の最小化 394 |
14.4 Schrijverのアルゴリズム 397 |
14.5 対称劣モジュラー関数 403 |
演習問題 405 |
参考文献 408 |
第15章 NP-完全性 411 |
15.1 チューリング機械 412 |
15.2 Churchの提唱 414 |
15.3 PとNP 419 |
15.4 Cookの定理 424 |
15.5 いくつかの基本的なNP-完全問題 428 |
15.6 クラスcoNP 436 |
15.7 NP-困難問題 438 |
演習問題 442 |
参考文献 446 |
第16章 近似アルゴリズム 448 |
16.1 集合カバー 449 |
16.2 最大カット問題 455 |
16.3 彩色 462 |
16.4 近似スキーム 470 |
16.5 最大充足化問題 473 |
16.6 PCP定理 479 |
16.7 L-帰着 483 |
演習問題 490 |
参考文献 494 |
第17章 ナップサック問題 499 |
17.1 小数ナップサック問題と重み付き中央値問題 499 |
17.2 擬似多項式時間アルゴリズム 502 |
17.3 完全多項式近似スキーム 504 |
演習問題 507 |
参考文献 508 |
第18章 ビンパッキング問題 510 |
18.1 グリーディ法 511 |
18.2 漸近的近似スキーム 517 |
18.3 Karmarkar-Karpアルゴリズム 521 |
演習問題 524 |
参考文献 526 |
第19章 多品種フローと辺素パス 529 |
19.1 多品種フロー 530 |
19.2 多品種フローのアルゴリズム 533 |
19.3 有向辺素パス問題 538 |
19.4 無向辺素パス問題 543 |
演習問題 549 |
参考文献 552 |
第20章 ネットワーク設計問題 556 |
20.1 シュタイナー木 557 |
20.2 Robins-Zelikovskyアルゴリズム 562 |
20.3 サバイバルネットワーク設計 569 |
20.4 主双対近似アルゴリズム 572 |
20.5 Jainのアルゴリズム 581 |
演習問題 588 |
参考文献 591 |
第21章 巡回セールスマン問題 595 |
21.1 TSPの近似アルゴリズム 595 |
21.2 ユークリッドTSP 601 |
21.3 局所探索 610 |
21.4 巡回セールスマン多面体 618 |
21.5 下界 624 |
21.6 分枝限定法 627 |
演習問題 629 |
参考文献 633 |
第22章 施設配置問題 637 |
22.1 容量制約なし施設配置問題 637 |
22.2 線形計画問題の解のラウンディング 639 |
22.3 主双対アルゴリズム 641 |
22.4 スケール変換とグリーディ増加操作 648 |
22.5 開設施設数の制約 652 |
22.6 局所探索 656 |
22.7 容量制約付き施設配置問題 663 |
22.8 普遍的施設配置問題 666 |
演習問題 675 |
参考文献 676 |
訳者あとがき 679 |
引用文献著者索引 682 |
問題・アルゴリズム索引 691 |
事項索引 698 |