内容紹介

組合せ最適化とは、対立する複数の制約を満たす有限個の解から最良の解を探し出すことである。扱う数はn個でも、解の個数はn!個というように膨大な数の組合せを考慮せねばならないので、高速に最良の解を求めるには数理的な理論と手法が不可欠。本書では、ネットワーク上の様々な問題を、組合せ理論・グラフ理論を用いてモデル化し、解決する。ほぼすべての定理に簡潔な証明があり、見出し語3000超の索引も充実、この第２版は、原著最新版に対応した完全アップデート版。単体法の実装法などに関する節が新たに追加。

目次

第１章　はじめに
　１．１　列挙
　１．２　アルゴリズムの計算時間
　１．３　線形の最適化問題
　１．４　ソーティング
第２章　グラフ
　２．１　基礎的な定義
　２．２　木，閉路，カット
　２．３　連結性
　２．４　オイラーグラフと２部グラフ
　２．５　平面性
　２．６　平面的双対性
第３章　線形計画法
　３．１　多面体
　３．２　単体法
　３．３　単体法の実装
　３．４　双対性
　３．５　凸包と有界多面体
第４章　線形計画アルゴリズム
　４．１　頂点と面のサイズ
　４．２　連分数
　４．３　ガウスの消去法
　４．４　楕円体法
　４．５　Khachiyanの定理
　４．６　分離問題と最適化
第５章　整数計画法
　５．１　多面体の整数包
　５．２　ユニモジュラー変換
　５．３　完全双対整数性
　５．４　完全ユニモジュラー行列
　５．５　切除平面法
　５．６　ラグランジュ緩和
第６章　全点木と有向木
　６．１　最小全点木問題
　６．２　最小重み有向木
　６．３　多面体的表現
　６．４　全点木と有向木のパッキング　
第７章　最短パス
　７．１　１点からの最短パス
　７．２　全点間の最短パス
　７．３　最小平均長閉路
第８章　ネットワークフロー
　８．１　最大フロー最小カット定理
　８．２　Mengerの定理
　８．３　Edmonds-Karpアルゴリズム
　８．４　ブロックフローと藤重（Fujishige）のアルゴリズム
　８．５　Goldberg-Tarjanアルゴリズム
　８．６　Gomory-Hu木
　８．７　無向グラフの最小容量カット
第９章　最小費用フロー
　９．１　問題の定式化
　９．２　最適性基準
　９．３　最小平均長閉路解消アルゴリズム
　９．４　最短パス反復アルゴリズム
　９．５　Orlinのアルゴリズム
　９．６　ネットワーク単体法
　９．７　時変フロー
第10章　最大マッチング
　10．１　２部グラフのマッチング
　10．２　Tutte行列
　10．３　Tutteの定理
　10．４　因子臨界的グラフの耳分離
　10．５　Edmondsのマッチングアルゴリズム
第11章　重み付きマッチング
　11．１　割当問題
　11．２　重み付きマッチングアルゴリズムの概略
　11．３　重み付きマッチングアルゴリズムの実装
　11．４　事後最適性
　11．５　マッチング多面体
第12章　b‐マッチングとT‐ジョイン
　12．１　b-マッチング
　12．２　最小重みT-ジョイン
　12．３　T-ジョインとTカット
　12．４　Padberg-Raoの定理
第13章　マトロイド
　13．１　独立性システムとマトロイド
　13．２　他のマトロイド公理系
　13．３　双対性
　13．４　グリーデイ法
　13．５　マトロイドの共通独立集合
　13．６　マトロイド分割
　13．７　重み付きマトロイド交差
第14章　マトロイドの一般化
　14．１　グリードイド
　14．２　ポリマトロイド
　14．３　劣モジュラー関数の最小化
　14．４　Schrijverのアルゴリズム
　14．５　対称劣モジュラー関数
第15章　ＮＰ‐完全性
　15．１　チューリング機械
　15．２　Churchの定理
　15．３　ＰとＮＰ
　15．４　Cookの定理
　15．５　いくつかの基本的なＮＰ-完全問題
　15．６　クラスｃｏＮＰ
　15．７　NP-困難問題
第16章　近似アルゴリズム
　16．１　集合カバー
　16．２　最大カット問題
　16．３　彩色
　16．４　近似スキーム
　16．５　最大充足化問題
　16．６　ＰＣＰ定理
　16．７　Ｌ-帰着
第17章　ナップサック問題
　17．１　少数ナップサック問題と重み付き中央値問題
　17．２　疑似多項式時間アルゴリズム
　17．３　完全多項式近似スキーム
第18章　ビンパッキング問題
　18．１　グリーデイ法
　18．２　漸近的近似スキーム
　18．３　Karmarkar-Karpアルゴリズム
第19章　多品種フローと辺素パス
　19．１　多品種フロー
　19．２　多品種フローのアルゴリズム
　19．３　有向辺素パス問題
　19．４　無向辺素パス問題
第20章　ネットワーク設計問題
　20．１　シュタイナー木
　20．２　Robins-Zelikovskyアルゴリズム
　20．３　サバイバルネットワーク設計
　20．４　主双対近似アルゴリズム
　20．５　Jainのアルゴリズム
第21章　巡回セールスマン問題
　21．１　ＴＳＰの近似アルゴリズム
　21．２　ユークリッドＴＳＰ
　21．３　局所探索
　21．４　巡回セールスマン多面体
　21．５　下界
　21．６　分枝限定法　
第22章　施設配置問題
　22．１　容量制約なし施設配置問題
　22．２　線形計画問題の解のラウンディング
　22．３　主双対アルゴリズム
　22．４　スケール変換とグリーデイ増加操作
　22．５　開設施設数の制約
　22．６　局所探索
　22．７　容量制約付き施設配置問題
　22．８　普遍的施設配置問題

出版社からのメッセージ

本書は改訂版『組合せ最適化 原書6版』（2022年11月刊）を刊行しています。

本書は、2009年３月にシュプリンガー・ジャパン株式会社より出版された同名書籍を再出版したものです。

------------------------------------------
本書は、書籍からスキャナによる読み取りを行い、印刷・製本を行っています。
一部、装丁が異なったり、印刷が不明瞭な場合がございますが、ご了承くださいますようお願い申し上げます。
------------------------------------------

関連商品

• 
  組合せ最適化 原書6版 理論とアルゴリズム 浅野　孝夫 訳
  浅野　泰仁 訳
  平田 富夫 訳
  
• 
  グラフ理論 山下　登茂紀 訳
  千葉　周也 訳
  
• 
  ヴァン・リント&ウィルソン 組合せ論 上 神保　雅一 監訳
  澤　正憲 訳
  萩田　真理子 訳
  
• 
  ヴァン・リント&ウィルソン 組合せ論 下 神保　雅一 監訳
  澤　正憲 訳
  萩田　真理子 訳
  
• 
  現代数学シリーズ 可換代数と組合せ論　復刊 日比　孝之 著
  伊藤　雄二 編