アルゴリズム特論I（近似アルゴリズム）
アルゴリズム特論I（近似アルゴリズム）
近似アルゴリズムの基礎を学習する．離散最適化問題の多くがＮＰ困難と呼ばれる問題であり，それらは，現実的な時間で最適解を求めることが不可能であると思われている問題である．そのような計算困難性に対処する一つの方法として，最適解に近い解，「近似解」を求めるアルゴリズムが考案されてきた．本講義では，そのようなアルゴリズム論の一分野である近似アルゴリズムの基礎を学習する．
講義スケジュール
導入（近似アルゴリズムとは：カット問題を例に）
巡回セールスマン問題
ナップサック問題
近似スキーム１（ＰＴＡＳ：ナップサック問題）
近似スキーム２（ＦＰＴＡＳ：ナップサック問題）
充足可能性問題１（貪欲法）
充足可能性問題２（乱択アルゴリズム）
充足可能性問題３（線形計画法の適用）
頂点彩色問題１（貪欲法）
頂点彩色問題２（半正定値計画法の適用）
最短ベクトル問題１（二次元アルゴリズム）
最短ベクトル問題２（グラム・シュミットの直交基底）
最短ベクトル問題３（LLL アルゴリズムの近似率）
最短ベクトル問題４（LLL アルゴリズムの計算時間）
Last Update: 02/April/2023