第I 部離散最適化問題とアルゴリズム
　1. 最小木問題
　　1. 1 最小木問題の定義
　　1. 2 全域木の性質
　　1. 3 最小木の最適性条件
　　1. 4 最小木のアルゴリズム
　　　1. 4. 1 全域木を求めるアルゴリズム
　　　1. 4. 2 クラスカルのアルゴリズム
　　　1. 4. 3 カラバのアルゴリズム
　　1. 5 章末ノート：離散凸解析への展望
　2. 最短路問題
　　2. 1 最短路問題の定義
　　2. 2 最短路の性質
　　2. 3 最短路のアルゴリズム
　　　2. 3. 1 距離ラベルを用いたアルゴリズムの一般形
　　　2. 3. 2 ダイクストラのアルゴリズム
　　　2. 3. 3 ベルマン・フォードのアルゴリズム
　　2. 4 章末ノート：離散凸解析への展望
　3. マッチング問題
　　3. 1 マッチング問題の定義
　　　3. 1. 1 2 部グラフの最大マッチング問題
　　　3. 1. 2 2 部グラフの最大重みマッチング問題
　　　3. 1. 3 一般グラフのマッチング問題
　　3. 2 マッチングと交互路
　　3. 3 2 部グラフのマッチングの性質
　　　3. 3. 1 補助グラフを用いた最適性条件
　　　3. 3. 2 最大マッチング最小被覆定理
　　3. 4 アルゴリズム
　　　3. 4. 1 最大マッチング問題のアルゴリズム
　　　3. 4. 2 最大重みk マッチング問題のアルゴリズム
　　3. 5 章末ノート：離散凸解析への展望
　4. 最大流問題
　　4. 1 最大流問題の定義
　　4. 2 最大フローの性質
　　　4. 2. 1 フローの分解
　　　4. 2. 2 カット容量
　　　4. 2. 3 残余ネットワーク
　　　4. 2. 4 最大フロー最小カット定理
　　4. 3 最大流問題のアルゴリズム
　　4. 4 需要供給制約を満たすフロー
　　4. 5 章末ノート：離散凸解析への展望
　5. 最小費用流問題
　　5. 1 最小費用流問題の定義
　　　5. 1. 1 最小費用流問題の基本形
　　　5. 1. 2 最小費用流問題の変種
　　　5. 1. 3 他の離散最適化問題との関係
　　5. 2 最小費用フローの性質
　　　5. 2. 1 残余ネットワーク
　　　5. 2. 2 ポテンシャル
　　5. 3 最小費用流問題のアルゴリズム
　　　5. 3. 1 負閉路消去アルゴリズム
　　　5. 3. 2 逐次最短路アルゴリズム
　　5. 4 最小費用流問題の双対問題
　　　5. 4. 1 定式化
　　　5. 4. 2 最適性条件
　　　5. 4. 3 最適性定理の証明
　　　5. 4. 4 ハッシンのアルゴリズム
　　　5. 4. 5 最適ポテンシャルの整数性
　　5. 5 最小費用流問題の一般化
　　　5. 5. 1 定式化
　　　5. 5. 2 最適性条件とアルゴリズム
　　5. 6 最小費用流問題の双対問題の一般化
　　　5. 6. 1 定式化
　　　5. 6. 2 最適性条件とアルゴリズム
　　5. 7 章末ノート：離散凸解析への展望
　6. 資源配分問題
　　6. 1 資源配分問題の定義
　　6. 2 単純な資源配分問題のアルゴリズム
　　　6. 2. 1 貪欲アルゴリズム
　　　6. 2. 2 貪欲アルゴリズムの高速化
　　6. 3 劣モジュラ制約付き資源配分問題
　　　6. 3. 1 様々な制約
　　　6. 3. 2 貪欲アルゴリズム
　　6. 4 章末ノート：離散凸解析への展望
第II 部離散凸解析の概要
　7. 凸解析
　　7. 1 凸集合と凸関数
　　7. 2 最小解
　　7. 3 ルジャンドル変換
　　7. 4 分離定理
　　7. 5 フェンシェル双対性
　　7. 6 章末ノート
　8. 一変数の離散凸関数
　　8. 1 定義
　　8. 2 最小解
　　8. 3 離散ルジャンドル変換
　　8. 4 離散分離定理
　　8. 5 離散フェンシェル双対性
　　8. 6 章末ノート
　9. 離散凸解析の基本概念
　　9. 1 M 凸関数
　　　9. 1. 1 M 凸関数の定義
　　　9. 1. 2 M 凸関数の例
　　9. 2 L 凸関数
　　　9. 2. 1 L 凸関数の定義
　　　9. 2. 2 L 凸関数の例
　　9. 3 離散凸関数のクラス
　　9. 4 章末ノート：離散凸解析の歴史
　10. 離散凸解析の基本定理
　　10. 1 離散関数の凸拡張
　　10. 2 最小解
　　10. 3 離散ルジャンドル変換と共役性定理
　　10. 4 離散分離定理
　　10. 5 離散フェンシェル双対性
　　　10. 5. 1 基本形
　　　10. 5. 2 和の最小化
　　10. 6 章末ノート
　11. 連続変数の離散凸関数
　　11. 1 M 凸関数
　　11. 2 L 凸関数
　　11. 3 章末ノート
第III 部離散凸最適化のアルゴリズム
　12. 離散凸関数最小化の手法
　　12. 1 貪欲アプローチ
　　　12. 1. 1 一変数離散凸関数の場合
　　　12. 1. 2 多変数離散凸関数の場合
　　　12. 1. 3 逐次追加型の貪欲アプローチ
　　12. 2 領域縮小アプローチ
　　　12. 2. 1 一変数離散凸関数の場合
　　　12. 2. 2 多変数離散凸関数の場合
　　12. 3 スケーリングアプローチ
　　　12. 3. 1 一変数離散凸関数の場合
　　　12. 3. 2 多変数離散凸関数の場合
　　12. 4 連続緩和アプローチ
　　　12. 4. 1 一変数離散凸関数の場合
　　　12. 4. 2 多変数離散凸関数の場合
　　12. 5 章末ノート
　13. L 凸関数最小化
　　13. 1 扱う問題
　　13. 2 貪欲アルゴリズム
　　13. 3 スケーリングアルゴリズム
　　13. 4 連続緩和アルゴリズム
　　13. 5 章末ノート
　14. M凸関数最小化
　　14. 1 扱う問題
　　　14. 1. 1 M 凸関数とM\\ 凸関数の制約なし最小化
　　　14. 1. 2 M\\ 凸関数の成分和制約付き最小化
　　　14. 1. 3 離散最適化問題との関係
　　14. 2 貪欲アルゴリズム
　　　14. 2. 1 M 凸関数の制約なし最小化
　　　14. 2. 2 M\\ 凸関数の制約なし最小化
　　　14. 2. 3 M\\ 凸関数の成分和制約付き最小化
　　14. 3 領域縮小アルゴリズム
　　　14. 3. 1 M 凸関数の制約なし最小化
　　　14. 3. 2 M\\ 凸関数の制約なし最小化
　　14. 4 スケーリングアルゴリズム
　　　14. 4. 1 M 凸関数の制約なし最小化
　　　14. 4. 2 M\\ 凸関数の成分和制約付き最小化
　　14. 5 連続緩和アルゴリズム
　　　14. 5. 1 M 凸関数の制約なし最小化
　　　14. 5. 2 M\\ 凸関数の成分和制約付き最小化
　　　14. 5. 3 単純な資源配分問題への適用
　　14. 6 章末ノート
　15. M凸関数の和の最小化
　　15. 1 扱う問題
　　15. 2 許容解の求め方
　　　15. 2. 1 M 凸集合の共通部分の要素を求める問題
　　　15. 2. 2 M 凸集合の性質
　　　15. 2. 3 補助問題の性質
　　　15. 2. 4 アルゴリズム
　　15. 3 最適解の求め方
　　　15. 3. 1 M 凸関数の性質
　　　15. 3. 2 最適性条件
　　　15. 3. 3 アルゴリズム
　　15. 4 章末ノート
文献
索引