内容紹介

本書は、近似アルゴリズム理論の最新の成果を、系統的に直観的にわかりやすくまとめた解説書。複雑で手強そうに見えるアルゴリズムも、そのアイディアを深く解釈して、単純明快に記述し、同時に新しい洞察も加えている。さらに豊富な例題や図解も盛り込み、読者の理解が深まるよう入念な工夫も施されている。

目次

第１章　はじめに
　１．１　ＯＰＴの下界法
　１．２　よい特徴付けをもつ問題と最小最大関係
　１．３　演習問題
　１．４　文献ノート
第I部　組合せアルゴリズム
　第２章　集合カバー
　　２．１　グリーディアルゴリズム
　　２．２　層別化
　　２．３　最短拡大ストリング問題への応用
　　２．４　演習問題
　　２．５　文献ノート
　第３章　シュタイナー木とＴＳＰ
　　３．１　メトリックシュタイナー木
　　３．２　メトリックＴＳＰ
　　３．３　演習問題
　　３．４　文献ノート
　第４章　多分割カットとｋ-カット
　　４．１　多分割カット問題
　　４．２　最小k-カット問題
　　４．３　演習問題
　　４．４　文献ノート
　第５章　ｋ-センター
　　５．１　パラメトリック刈り取り法のメトリックk-センター問題への適用
　　５．２　重み付き板
　　５．３　演習問題
　　５．４　文献ノート
　第６章　フィードバック点集合
　　６．１　閉路階数的重み付きグラフ
　　６．２　フィードバック点集合への層別化の適用
　　６．３　演習問題
　　６．４　文献ノート
　第７章　最短拡大ストリング
　　７．１　近似率４のアルゴリズム
　　７．２　近似率３への改善
　　７．３　演習問題
　　７．４　文献ノート
　第８章　ナップサック
　　８．１　ナップサック問題に対する擬多項式時間アルゴリズム
　　８．２　ナップサック問題に対するＦＰＴＡＳ
　　８．３　強ＮＰ-困難性とＦＰＴＡＳの存在
　　８．４　演習問題
　　８．５　文献ノート
　第９章　ビンパッキング
　　９．１　漸近的ＰＴＡＳ
　　９．２　演習問題
　　９．３　文献ノート
　第10章　終了時刻最小化スケジューリング
　　10．１　２近似アルゴリズム
　　10．２　終了時刻最小化スケジューリング問題に対するＰＴＡＳ
　　10．３　演習問題
　　10．４　文献ノート　
　第11章　ユークリッド空間のＴＳＰ
　　11．１　アルゴリズム
　　11．２　正当性の証明
　　11．３　演習問題
　　11．４　文献ノート
第II部　ＬＰに基づくアルゴリズム
　第12章　ＬＰ-双対性入門
　　12．１　ＬＰ-双対定理
　　12．２　最小最大関係とＬＰ-双対性
　　12．３　２つの基本アルゴリズム設計技法
　　12．４　演習問題
　　12．５　文献ノート
　第13章　双対フィット法による集合カバー
　　13．１　グリーディ集合カバーアルゴリズムの双対フィット法に基づく解析
　　13．２　集合カバーの一般化
　　13．３　演習問題
　　13．４　文献ノート
　第14章　集合カバーへのラウンディングの適用
　　14．１　単純なラウンディングアルゴリズム
　　14．２　乱数使用ラウンディング
　　14．３　点カバー問題の半整数性
　　14．４　演習問題
　　14．５　文献ノート
　第15章　プライマルデュアル法による集合カバー
　　15．１　プライマルデュアル法の概観
　　15．２　プライマルデュアル法の集合カバーへの適用
　　15．３　演習問題
　　15．４　文献ノート
　第16章　最大充足化問題
　　16．１　長いクローズの取り扱い
　　16．２　条件付き期待値法による脱ランダム化
　　16．３　ＬＰ-ラウンディングによる短いクローズの取り扱い
　　16．４　３／４近似アルゴリズム
　　16．５　演習問題
　　16．６　文献ノート
　第17章　相互無関係並列マシーンのスケジューリング
　　17．１　ＬＰ設定におけるパラメトリック刈り取り
　　17．２　端点解の性質
　　17．３　アルゴリズム
　　17．４　端点解の性質
　　17．５　演習問題
　　17．６　文献ノート
　第18章　木における多点対カットと整数多品種フロー
　　18．１　問題とそのＬＰ-緩和
　　18．２　プライマルデュアル法に基づくアルゴリズム
　　18．３　演習問題
　　18．４　文献ノート
　第19章　多分割カット
　　19．１　興味深いＬＰ-緩和
　　19．２　乱数使用ラウンディングアルゴリズム
　　19．３　点型多分割カット問題の半整数性
　　19．４　演習問題
　　19．５　文献ノート
　第20章　一般のグラフの多点対カット
　　20．１　総流量最大多品種フロー
　　20．２　ＬＰ-ラウンディングに基づくアルゴリズム
　　20．３　タイトな例
　　20．４　多点対カットの応用
　　20．５　演習問題
　　20．６　文献ノート
　第21章　最適スパースカット
　　21．１　スループット最大多品種フロー
　　21．２　線形計画問題としての定式化
　　21．３　メトリック，カットパッキングおよびℓ1埋め込み可能性
　　21．４　メトリックに対する低歪みℓ1-埋め込み
　　21．５　ＬＰ-ラウンディングに基づくアルゴリズム
　　21．６　応用
　　21．７　演習問題
　　21．８　文献ノート
　第22章　シュタイナー森
　　22．１　ＬＰ-緩和と双対問題
　　22．２　同期的プライマルデュアル法
　　22．３　解析
　　22．４　演習問題
　　22．５　文献ノート　
　第23章　シュタイナーネットワーク
　　23．１　ＬＰ-緩和と半整数性
　　23．２　反復ラウンディングの技法
　　23．３　端点解の特徴付け
　　23．４　数え上げ議論
　　23．５　演習問題
　　23．６　文献ノート
　第24章　施設配置
　　24．１　双対問題の直感的理解
　　24．２　主相補条件の緩和
　　24．３　プライマルデュアル法に基づくアルゴリズム
　　24．４　解析
　　24．５　演習問題
　　24．６　文献ノート
　第25章　ｋ-メディアン
　　25．１　ＬＰ-緩和と双対問題
　　25．２　ハイレベルのアイデア
　　25．３　乱数使用ラウンディング
　　25．４　近似アルゴリズムに対するラグランジュ緩和の技法
　　25．５　演習問題
　　25．６　文献ノート
　 第26章　半正定値計画法
　　26．１　厳密２次計画問題とベクトル計画問題
　　26．２　半正定値行列の性質
　　26．３　半正定値計画問題
　　26．４　乱数使用ラウンディングアルゴリズム
　　26．５　ＭＡＸ-２ＳＡＴに対する近似保証の改善
　　26．６　演習問題
　　26．７　文献ノート
第III部　他のトピックス
　第27章　最短ベクトル
　　27．１　基底，行列式，直交性近似率
　　27．２　ユークリッドのアルゴリズムとガウスのアルゴリズム
　　27．３　Gram-Schmidtの直交化を用いて得られるＯＰＴの下界
　　27．４　n次元への拡張
　　27．５　双対格子とアルゴリズムの観点からの有用性
　　27．６　演習問題
　　27．７　文献ノート
　第28章　数え上げ問題
　　28．１　ＤＮＦ解の数え上げ
　　28．２　ネットワーク信頼性
　　28．３　演習問題
　　28．４　文献ノート
　第29章　近似の困難性
　　29．１　リダクション，ギャップ，および近似困難性
　　29．２　ＰＣＰ定理
　　29．３　ＭＡＸ-３ＳＡＴの近似困難性
　　29．４　変数の出現回数に制限のあるＭＡＸ-３ＳＡＴの近似困難性
　　29．５　点カバーとシュタイナー木の近似困難性
　　29．６　クリークの近似困難性
　　29．７　集合カバーの近似困難性
　　29．８　演習問題
　第30章　オープン問題
　　30．１　定数近似のアルゴリズムをもつ問題
　　30．２　他の最適化問題
　　30．３　数え上げ問題
　　30．４　文献ノート
付録Ａ　アルゴリズム設計者のための計算の複雑さの理論の概観
　Ａ．１　証明とクラスＮＰ
　Ａ．２　リダクションとＮＰ-完全性
　Ａ．３　ＮＰ-最適化問題と近似アルゴリズム
　Ａ．４　乱数使用の計算量クラス
　Ａ．５　自己リダクション可能性
　Ａ．６　文献ノート　　　　
付録Ｂ　確率論からの基本事項
　Ｂ．１　期待値と分散
　Ｂ．２　平均からの偏差
　Ｂ．３　基本分布
　Ｂ．４　文献ノート

出版社からのメッセージ

本書は、2002年11月にシュプリンガー・ジャパン株式会社より出版された同名書籍を再出版したものです。
------------------------------------------
本書は、少部数印刷にて重版が可能です。
在庫僅少の場合でもご注文いただけますので、お問い合わせください。
------------------------------------------
本書は、書籍からスキャナによる読み取りを行い、印刷・製本を行っています。
一部、装丁が異なったり、印刷が不明瞭な場合がございますが、ご了承くださいますようお願い申し上げます。
------------------------------------------

関連商品

• 
  アルゴリズム設計マニュアル 上 平田 富夫 訳
  
• 
  アルゴリズム設計マニュアル 下 平田 富夫 訳