アルゴリズム特論Ⅰ　--- 近似アルゴリズム ---

近似アルゴリズムの基礎を学習する． 離散最適化問題の多くがＮＰ困難と呼ばれる問題であり， それらは， 現実的な時間で最適解を求めることが不可能であると思われている問題である． そのような計算困難性に対処する一つの方法として， 最適解に近い解，「近似解」を求めるアルゴリズムが考案されてきた． 本講義では， そのようなアルゴリズム論の一分野である近似アルゴリズムの基礎を学習する．

• 講義資料

講義スケジュール

1. 導入（近似アルゴリズムとは）
2. カット問題
3. 集合被覆問題
4. 頂点被覆問題
5. 独立頂点集合問題
6. 巡回セールスマン問題
7. ナップサック問題
8. 近似スキーム１（ＰＴＡＳ：ナップサック問題）
9. 近似スキーム２（ＦＰＴＡＳ：ナップサック問題）
10. 充足可能性問題１（貪欲法）
11. 充足可能性問題２（乱択アルゴリズム）
12. 充足可能性問題３（線形計画法の適用）
13. 頂点彩色問題１（貪欲法）
14. 頂点彩色問題２（半正定値計画法の適用）