近似アルゴリズムデザイン [単行本]
    • 近似アルゴリズムデザイン [単行本]

    • ¥13,200396ポイント(3%還元)
    • お取り寄せ
100000009002420015

近似アルゴリズムデザイン [単行本]

価格:¥13,200(税込)
ポイント:396ポイント(3%還元)(¥396相当)
お届け日:お取り寄せこの商品は、日時を指定できません。届け先変更]詳しくはこちら
出版社:共立出版
販売開始日: 2015/09/23
お取り扱い: のお取り扱い商品です。
ご確認事項:返品不可

カテゴリランキング

店舗受け取りが可能です
NEWマルチメディアAkibaマルチメディア梅田マルチメディア博多にて24時間営業時間外でもお受け取りいただけるようになりました

近似アルゴリズムデザイン [単行本] の 商品概要

  • 目次

    第I部 技法:入門

    第1章 近似アルゴリズムへの序論
    1.1 近似アルゴリズムとは? なぜ近似アルゴリズムなのか?
    1.2 技法と線形計画への序論:集合カバー問題
    1.3 確定的ラウンディングアルゴリズム
    1.4 双対解によるラウンディング
    1.5 双対解の構成:主双対法
    1.6 グリーディアルゴリズム
    1.7 乱択ラウンディングアルゴリズム

    第2章 グリーディアルゴリズムと局所探索アルゴリズム
    2.1 単一マシーンによる期限付きジョブのスケジューリング
    2.2 k-センター問題
    2.3 同一並列マシーン上でのジョブのスケジューリング
    2.4 巡回セールスマン問題
    2.5 銀行口座の浮動資金の最大化
    2.6 最小次数全点木問題に対する局所探索アルゴリズム
    2.7 辺彩色

    第3章 データのラウンディングと動的計画
    3.1 ナップサック問題
    3.2 同一並列マシーン上でのジョブのスケジューリング
    3.3 ビンパッキング問題

    第4章 線形計画問題での確定的ラウンディング
    4.1 単一マシーンによるジョブの完了時刻の和の最小化スケジューリング
    4.2 単一マシーンによるジョブの重み付き完了時刻の和の最小化
    4.3 大規模線形計画問題の楕円体法による多項式時間解法
    4.4 賞金獲得シュタイナー木問題
    4.5 容量制約なし施設配置問題
    4.6 ビンパッキング問題

    第5章 ランダムサンプリングと線形計画問題での乱択ラウンディング
    5.1 MAXSATとMAXCUTに対する単純なアルゴリズム
    5.2 脱乱択
    5.3 偏りのあるコイン投げ
    5.4 乱択ラウンディング
    5.5 二つの解の良いほうの解を選択する
    5.6 非線形乱択ラウンディング
    5.7 賞金獲得シュタイナー木問題
    5.8 容量制約なし施設配置問題
    5.9 単一マシーンによるジョブの重み付き完了時刻の和の最小化
    5.10 Chernoff限界
    5.11 整数多品種フロー
    5.12 ランダムサンプリングと3-彩色可能デンスグラフの彩色

    第6章 半正定値計画問題での乱択ラウンディング
    6.1 半正定値計画の簡単な紹介
    6.2 大きいカットを求める
    6.3 二次計画問題の近似解
    6.4 相関クラスタリングを求める
    6.5 3-彩色可能グラフの彩色

    第7章 主双対法
    7.1 集合カバー問題:復習
    7.2 値を増加する変数の選択:無向グラフのフィードバック点集合問題
    7.3 主解の整理:最短s-tパス問題
    7.4 複数の変数の値の同時増加:一般化シュタイナー木問題
    7.5 不等式の強化:最小ナップサック問題
    7.6 容量制約なし施設配置問題
    7.7 ラグランジュ緩和とk-メジアン問題

    第8章 カットとメトリック
    8.1 多分割カット問題と最小カットに基づくアルゴリズム
    8.2 多分割カット問題とLPラウンディングアルゴリズム
    8.3 多点対カット問題
    8.4 平衡カット
    8.5 木メトリックによるメトリックの確率的近似
    8.6 木メトリックの応用:まとめ買いネットワーク設計
    8.7 メトリックの延伸と木メトリックと線形アレンジメント


    第II部 技法:発展

    第9章 グリーディアルゴリズムと局所探索アルゴリズムの発展利用
    9.1 容量制約なし施設配置問題に対する局所探索アルゴリズム
    9.2 k-メディアン問題に対する局所探索アルゴリズム
    9.3 最小次数全点木
    9.4 容量制約なし施設配置問題に対するグリーディアルゴリズム

    第10章 データのラウンディングと動的計画の発展利用
    10.1 ユークリッド平面上の巡回セールスマン問題
    10.2 平面的グラフの最大独立集合

    第11章 線形計画問題での確定的ラウンディングの発展利用
    11.1 一般化割当て問題
    11.2 最小コスト次数上界付き全点木
    11.3 サバイバルネットワーク設計と反復ラウンディング

    第12章 ランダムサンプリングと乱択ラウンディングの発展利用
    12.1 容量制約なし施設配置問題
    12.2 単一ソースのレンタル・購入問題
    12.3 シュタイナー木問題
    12.4 すべてを同時に解決:デンスグラフの大きいカットの求解

    第13章 半正定値計画問題での乱択ラウンディングの発展利用
    13.1 二次計画問題の近似
    13.2 3-彩色可能グラフの彩色
    13.3 ユニークゲーム

    第14章 主双対法の発展利用
    14.1 賞金獲得シュタイナー木問題
    14.2 無向グラフのフィードバック点集合問題

    第15章 カットとメトリックの発展利用
    15.1 低歪み埋め込みと最疎カット問題
    15.2 需要未確定ルーティングとカット木パッキング
    15.3 カット木パッキングと最小二等分割問題
    15.4 一様最疎カット問題

    第16章 近似困難性の証明技法
    16.1 近似保存リダクション
    16.2 確率的検証可能証明からのリダクション
    16.3 ラベルカバー問題からのリダクション
    16.4 ユニークゲーム問題からのリダクション

    第17章 未解決問題

    付録A 線形計画
    付録B NP-完全性
  • 著者紹介(「BOOK著者紹介情報」より)(本データはこの書籍が刊行された当時に掲載されていたものです)

    浅野 孝夫(アサノ タカオ)
    中央大学理工学部情報工学科教授。1977年東北大学にて工学博士取得。1987年日本IBM科学賞(情報科学部門)受賞
  • 内容紹介

     本書は,近似アルゴリズムデザインの技法とアイデアを系統的かつ明快に解説している。 第1部では,単純な問題を例にとり,これらの技法とアイデアを具体的にわかりやすく解説している。第2部では,これらの技法とアイデアを実際のケースで生じるより高度な問題に適用する際の工夫を具体的に解説している。
     本書において系統的な解説を可能にしているのが,線形計画法と整数計画法である。欧米の大学では,本当に実用的なアルゴリズムの研究開発には,これらの分野が極めて重要であることが認識されてきている。したがって,情報科学系でもこれらを講義で取り上げる大学が増加してきていて,本書もそれに後押しされて,その重要性を増してきている。すなわち,これからのアルゴリズム教育には,線形計画法と整数計画法の概念の理解とそれを応用する能力の育成が必要不可欠となると思われるが,本書はそれらも自然に身につくように記述されている。
    (David P. Williamson, David B. Shmoys:The Design of Approximation Algorithms, Cambridge University Press, 2011)

近似アルゴリズムデザイン [単行本] の商品スペック

商品仕様
出版社名:共立出版
著者名:デイビッド・P. ウィリアムソン(著)/デイビッド・B. シュモイシュ(著)/浅野 孝夫(訳)
発行年月日:2015/09/25
ISBN-10:4320123913
ISBN-13:9784320123915
判型:規大
対象:専門
発行形態:単行本
内容:数学
言語:日本語
ページ数:591ページ
縦:27cm
その他: 原書名: The Design of Approximation Algorithms〈Williamson,David P.;Shmoys,David B.〉
他の共立出版の書籍を探す

    共立出版 近似アルゴリズムデザイン [単行本] に関するレビューとQ&A

    商品に関するご意見やご感想、購入者への質問をお待ちしています!