内容紹介
組合せ最適化は，組合せ理論，オペレーションズリサーチ，および理論情報科学にルーツを持つ比較的新しい離散数学の研究分野である．
現実の多くの問題が組合せ最適化の問題として抽象化され定式化できることから，現在では最も活発な研究分野の1つとなり，離散数学の研究の駆動力になっていると言えるだろう．
本書は高度な内容の教科書としても研究用の参考書としても有用であることを目標とし，組合せ最適化における最も重要な概念，理論的成果，およびアルゴリズムを解説している．
各章末には多数の演習問題を与え，その章で取り上げた話題に対するさらなる成果と応用なども含んでいる．
組合せ最適化のすべてを完璧に取り上げた本など書けるはずもなく，成長し発展するこの分野を包括的に解説することはますます困難になってきているが，改訂を重ねた本書は研究用としても教育用としても，ますます利用しやすく信頼できるものになっているだろう．
目次
記法一覧
問題一覧
アルゴリズム一覧
第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 普遍的施設配置問題
演習問題
参考文献
引用文献著者索引
問題・アルゴリズム索引
事項索引
出版社からのメッセージ
本書は『組合せ最適化 第2版』（2012年1月刊）の改訂版です。
