組合せ最適化 第2版

組合せ最適化 第2版

理論とアルゴリズム
原書名 Combinatorial Optimization
著者名 浅野 孝夫
浅野 泰仁
小野 孝男
平田 富夫
発行元 丸善出版
発行年月日 2012年01月
判型 B5変
ページ数 740ページ
ISBN 978-4-621-06202-9
Cコード 3041
ジャンル 数学・統計学 >  解析学

内容紹介

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

目次

第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 最小平均長閉路
第8章 ネットワークフロー
 8.1 最大フロー最小カット定理
 8.2 Mengerの定理
 8.3 Edmonds-Karpアルゴリズム
 8.4 ブロックフローと藤重(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 対称劣モジュラー関数
第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 完全多項式近似スキーム
第18章 ビンパッキング問題
 18.1 グリーデイ法
 18.2 漸近的近似スキーム
 18.3 Karmarkar-Karpアルゴリズム
第19章 多品種フローと辺素パス
 19.1 多品種フロー
 19.2 多品種フローのアルゴリズム
 19.3 有向辺素パス問題
 19.4 無向辺素パス問題
第20章 ネットワーク設計問題
 20.1 シュタイナー木
 20.2 Robins-Zelikovskyアルゴリズム
 20.3 サバイバルネットワーク設計
 20.4 主双対近似アルゴリズム
 20.5 Jainのアルゴリズム
第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 普遍的施設配置問題

出版社からのメッセージ

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

------------------------------------------
本書は、少部数印刷にて重版が可能です。
在庫僅少の場合でもご注文いただけますので、お問い合わせください。
------------------------------------------
本書は、書籍からスキャナによる読み取りを行い、印刷・製本を行っています。
一部、装丁が異なったり、印刷が不明瞭な場合がございますが、ご了承くださいますようお願い申し上げます。
------------------------------------------

関連商品

定価:13,200円
(本体12,000円+税10%)
在庫:在庫あり