内容説明
本書では、得られる近似解の近似性能を保証するアルゴリズムについて、わかりやすく解説。とくに、近似性能の上界を下げるためには、より良い近似性能をもつアルゴリズムを設計し解析しなければならないが、そのための系統的な設計解析法である数理計画に基づくアルゴリズムに焦点を当てて、代表的な問題で具体例を通して、懇切丁寧に解説する。
目次
近似アルゴリズムの基礎
クラスＰＴＡＳ
クラスＦＰＴＡＳ
クラスｌｏｇ‐ＡＰＸとクラスｐｏｌｙ‐ＡＰＸ
線形計画と整数計画
線形計画による近似アルゴリズムデザイン
施設配置問題
ｋ‐センター問題とｋ‐メディアン問題
シュタイナー森問題
最大充足化問題に対する確率的方法
半正定値計画問題での乱択ラウンディング
