内容

目次

記法一覧 問題一覧 アルゴリズム一覧 第1章　はじめに 1.1 列挙 1.2 アルゴリズムの計算時間 1.3 線形の最適化問題 1.4 ソーティング 演習問題 参考文献 第2章　グラフ 2.1 基礎的な定義 2.2 木，閉路，カット 2.3 連結性 2.4 オイラーグラフと2部グラフ 2.5 平面性 2.6 平面的双対性 演習問題 参考文献 第3章　線形計画法 3.1 多面体 3.2 単体法 3.3 単体法の実装 3.4 双対性 3.5 凸包と有界多面体 演習問題 参考文献 第4章　線形計画アルゴリズム 4.1 頂点と面のサイズ 4.2 連分数 4.3 ガウスの消去法 4.4 楕円体法 4.5 Khachiyanの定理 4.6 分離問題と最適化 演習問題 参考文献 第5章　整数計画法 5.1 多面体の整数包 5.2 ユニモジュラー変換 5.3 完全双対整数性 5.4 完全ユニモジュラー行列 5.5 切除平面法 5.6 ラグランジュ緩和 演習問題 参考文献 第6章　全点木と有向木 6.1 最小全点木問題 6.2 最小重み有向木 6.3 多面体的表現 6.4 全点木と有向木のパッキング 演習問題 参考文献 第7章　最短パス 7.1 1点からの最短パス 7.2 全点間の最短パス 7.3 最小平均長閉路 7.4 薄軽木 演習問題 参考文献 第8章　ネットワークフロー 8.1 最大フロー最小カット定理 8.2 Mengerの定理 8.3 Edmonds-Karpアルゴリズム 8.4 DinicとKarzanovとFujishigeのアルゴリズム 8.5 Goldberg-Tarjanアルゴリズム 8.6 Gomory-Hu木 8.7 無向グラフの最小容量カット 演習問題 参考文献 第9章　最小費用フロー 9.1 問題の定式化 9.2 最適性基準 9.3 最小平均長閉路解消アルゴリズム 9.4 最短パス反復アルゴリズム 9.5 Orlinのアルゴリズム 9.6 ネットワーク単体法 9.7 時変フロー 演習問題 参考文献 第10章　最大マッチング 10.1 2部グラフのマッチング 10.2 Tutte行列 10.3 Tutteの定理 10.4 因子臨界的グラフの耳分解 10.5 Edmondsのマッチングアルゴリズム 演習問題 参考文献 第11章　重み付きマッチング 11.1 割当問題 11.2 重み付きマッチングアルゴリズムの概略 11.3 重み付きマッチングアルゴリズムの実装 11.4 事後最適性 11.5 マッチング多面体 演習問題 参考文献 第12章　b-マッチングとT-ジョイン 12.1 b-マッチング 12.2 最小重みT-ジョイン 12.3 T-ジョインとT-カット 12.4 Padberg-Raoの定理 演習問題 参考文献 第13章　マトロイド 13.1 独立性システムとマトロイド 13.2 他のマトロイド公理系 13.3 双対性 13.4 グリーディ法 13.5 マトロイドの共通独立集合 13.6 マトロイド分割 13.7 重み付きマトロイド交差 演習問題 参考文献 第14章　マトロイドの一般化 14.1 グリードイド 14.2 ポリマトロイド 14.3 劣モジュラー関数の最小化 14.4 Schrijverのアルゴリズム 14.5 対称劣モジュラー関数 14.6 劣モジュラー関数の最大化 演習問題 参考文献 第15章　NP-完全性 15.1 チューリング機械 15.2 Churchの提唱 15.3 PとNP 15.4 Cookの定理 15.5 いくつかの基本的なNP-完全問題 15.6 クラスcoNP 15.7 NP-困難問題 演習問題 参考文献 第16章　近似アルゴリズム 16.1 集合カバー 16.2 最大カット問題 16.3 彩色 16.4 近似スキーム 16.5 最大充足化問題 16.6 PCP定理 16.7 L-帰着 演習問題 参考文献 第17章　ナップサック問題 17.1 小数ナップサック問題と重み付き中央値問題 17.2 擬多項式時間アルゴリズム 17.3 完全多項式時間近似スキーム 17.4 多次元ナップサック問題 17.5 Nemhauser-Ullmannアルゴリズム 演習問題 参考文献 第18章　ビンパッキング問題 18.1 グリーディヒューリスティック 18.2 漸近的多項式時間近似スキーム 18.3 Karmarkar-Karpアルゴリズム 演習問題 参考文献 第19章　多品種フローと辺素パス 19.1 多品種フロー 19.2 多品種フローのアルゴリズム 19.3 最疎カットおよび最大フロー最小カット比 19.4 Leighton-Raoの定理 19.5 有向辺素パス問題 19.6 無向辺素パス問題 演習問題 参考文献 第20章　ネットワーク設計問題 20.1 シュタイナー木 20.2 Robins-Zelikovskyアルゴリズム 20.3 有向成分LPのラウンディング 20.4 サバイバルネットワーク設計 20.5 主双対近似アルゴリズム 20.6 Jainのアルゴリズム 20.7 VPN問題 演習問題 参考文献 第21章　巡回セールスマン問題 21.1 TSPの近似アルゴリズム 21.2 ユークリッドTSP 21.3 局所探索 21.4 巡回セールスマン多面体 21.5 下界 21.6 分枝限定法 演習問題 参考文献 第22章　施設配置問題 22.1 容量制約なし施設配置問題 22.2 線形計画問題の解のラウンディング 22.3 主双対アルゴリズム 22.4 スケール変換とグリーディ増加操作 22.5 開設施設数の制約 22.6 局所探索 22.7 容量制約付き施設配置問題 22.8 普遍的施設配置問題 演習問題 参考文献 引用文献著者索引 問題・アルゴリズム索引 事項索引