組合せ最適化への招待

SGCライブラリ  192

組合せ最適化への招待

モデルとアルゴリズム
定価:
2,640
(本体:2,400円+税)
難易度:中級

発行日:2024年7月25日

発行:サイエンス社

ISBN:978-4-7819-1609-5

サイズ:並製B5

ページ数:216ページ

在庫:在庫あり

内容詳細

組合せ最適化は,ルート探索やスケジューリングなど実社会に現れる課題を解決するために有用であるが,そこでは適切な定式化(モデリング)と効率的な計算方法(アルゴリズム)の設計が求められる.本書では,組合せ最適化の理論的な基礎に焦点を当て,特に,組合せ最適化問題の解きやすさ・解きにくさの背後にある理論的な性質を知ることを目指した.

目次

第I部 組合せ最適化の基礎
第1章 組合せ最適化
  1.1 組合せ最適化
  1.2 組合せ最適化問題へのモデル化
  1.3 計算の効率
  1.4 補足:組合せ爆発

第2章 線形最適化の基礎
  2.1 線形最適化問題
  2.2 双対定理
  2.3 多面体
  2.4 線形最適化問題と多面体
  2.5 線形最適化問題の解法

第3章 組合せ最適化モデル
  3.1 グラフ
  3.2 整数最適化問題
  3.3 組合せ最適化モデルの諸例

第II部 効率的に解ける組合せ最適化問題
第4章 二部グラフのマッチング
  4.1 最大マッチング問題の最大最小定理
  4.2 増加パスを用いた最大マッチングの特徴付け
  4.3 増加パスに基づくアルゴリズム
  4.4 より高速なアルゴリズム
  4.5 補足:良い特徴付け

第5章 二部グラフの最小コストの完全マッチング
  5.1 完全マッチング多面体
  5.2 完全マッチング多面体の線形不等式表現
  5.3 組合せ的なアルゴリズム

第6章 整数多面体と完全単模行列
  6.1 整数多面体
  6.2 完全単模行列
  6.3 完全単模行列と多面体の整数性
  6.4 完全単模行列の例
  6.5 完全単模行列の特徴付け

第7章 完全単模行列の組合せ最適化への応用
  7.1 二部グラフのマッチングと辺被覆
  7.2 フローとカット
  7.3 最短パス問題

第8章 完全双対整数性と一般のグラフのマッチング
  8.1 完全双対整数性
  8.2 一般のグラフのマッチング 

第9章 全域木とマトロイド
  9.1 全域木の性質
  9.2 マトロイド
  9.3 マトロイドの独立集合,ランク関数,サーキット
  9.4 最小基問題
  9.5 マトロイド多面体

第10章 最小カットと対称劣モジュラ関数
  10.1 最小カット問題
  10.2 最大隣接順序によるアルゴリズム
  10.3 辺数最小のカットを求める乱択アルゴリズム
  10.4 辺数最小のカットを求めるアルゴリズムの改良

第11章 線形代数を利用したアルゴリズム
  11.1 グラフと行列
  11.2 完全マッチングの存在を判定するアルゴリズム
  11.3 完全マッチングを求めるアルゴリズム

第III部 解きにくい組合せ最適化問題に対するアプローチ
第12章 近似アルゴリズム
  12.1 近似アルゴリズムとは
  12.2 ナップサック問題に対する近似アルゴリズム

第13章 集合被覆問題に対する近似アルゴリズム
  13.1 貪欲法
  13.2 線形最適化緩和
  13.3 貪欲法と線形最適化緩和
  13.4 線形最適化を用いた最適解の構成法
  13.5 主双対近似アルゴリズム

第14章 固定パラメータアルゴリズム
  14.1 固定パラメータアルゴリズムとは
  14.2 カーネル化
  14.3 頂点被覆問題に対するカーネル化アルゴリズム
  14.4 限定探索木
  14.5 線形最適化緩和の最適値との差をパラメータとしたアルゴリズム

第15章 オンラインマッチング
  15.1 オンラインマッチング問題とは
  15.2 貪欲法
  15.3 ランキングアルゴリズム
  15.4 ランキングアルゴリズムの競合比の解析

付録A アルゴリズムの基礎
  A.1 アルゴリズム
  A.2 計算複雑度
  A.3 オーダー記法
  A.4 アルゴリズムの入力のサイズ

文献ノート
参考文献
索引

サポート情報

関連書籍