近似アルゴリズム

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