近似アルゴリズム

離散最適化問題への効果的アプローチ
アルゴリズム・サイエンスシリーズ　１１（数理技法編）

共立出版
浅野孝夫　

• 価格: 4,400円（本体4,000円＋税）
• 発行年月: 2019年06月
• 判型: Ａ５
• ISBN: 9784320121775

内容情報

[BOOKデータベースより]

近似アルゴリズムの基礎
クラスＰＴＡＳ
クラスＦＰＴＡＳ
クラスｌｏｇ‐ＡＰＸとクラスｐｏｌｙ‐ＡＰＸ
線形計画と整数計画
線形計画による近似アルゴリズムデザイン
施設配置問題
ｋ‐センター問題とｋ‐メディアン問題
シュタイナー森問題
最大充足化問題に対する確率的方法
半正定値計画問題での乱択ラウンディング

[日販商品データベースより]

離散最適化問題は，現実世界で起こる様々な問題を抽象化した最適化問題で，機械学習も含めて多くの分野で注目されている。しかしながら，それらの問題では，高速に最適解を求めることができないことも多く，実際には，高性能の近似解を高速に求めて代用することが多い。このような状況下での近似アルゴリズム理論の研究は，得られる近似解の近似性能を保証するアルゴリズムの研究とも言える。
　そこで，本書では，得られる近似解の近似性能を保証するアルゴリズムについて，わかりやすく解説する。とくに，近似性能の上界を下げるためには，より良い近似性能をもつアルゴリズムを設計し解析しなければならないが，そのための系統的な設計解析法である数理計画に基づくアルゴリズムに焦点を当てて，代表的な問題で具体例を通して，懇切丁寧に解説する。また，近似性能の下界を明らかにするための標準的な技法についても簡単に触れる。さらに，近似性能に応じて問題が分類できることも示す。