組合せ最適化への招待

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

【主要目次】第I部：組合せ最適化の基礎（組合せ最適化／線形最適化の基礎／組合せ最適化モデル）／第II部：効率的に解ける組合せ最適化問題（二部グラフのマッチング／二部グラフの最小コストの完全マッチング／整数多面体と完全単模行列／完全単模行列の組合せ最適化への応用／完全双対整数性と一般のグラフのマッチング／全域木とマトロイド／最小カットと対称劣モジュラ関数／線形代数を利用したアルゴリズム）／第III部：解きにくい組合せ最適化問題に対するアプローチ（近似アルゴリズム／集合被覆問題に対する近似アルゴリズム／固定パラメータアルゴリズム／オンラインマッチング）／付録A：アルゴリズムの基礎／文献ノート