Approximation Algorithms Part I Week 2

　Week2 の講義を視聴した。Week2のテーマはナップサック問題だった。

　ナップサック問題は、動的計画法の基礎中の基礎ということで、プロコンで何度も解いているので最初の方はだいたい知っている話だった。価値が小さな整数の場合は多項式時間の動的計画法で解けるが、任意の実数の場合はどうすればよいか？ Scaling、Roundingというテクニックを使うことで近似解を求めることができる。

　Roundingのテクニックは Week1 の vertex cover にも出来てたが、vertex cover の場合は LP relaxation を解いた出力を rounding するのに対して、ナップサック問題の場合は 入力値を rounding する。アイデア自体はシンプルで実数を整数に変換して動的計画で解けばOK。

　Scalingのパラメータの取り方によって、任意のε > 0 に対して|OPT - ApproximationOPT| < εとなるような近似問題を定式化できるが、実行時間は1/εに対して線形で増えていくので実用的には程よいεを見極める必要がある。このあたりの reasoning/analysis は面白かった。

　

Approximation Algorithms Part I Week 1

　Courseraで「Approximation Algorithms Part I」という講義を取り始めた。以下のようなことを教えてくれる。

• クラスNPの組み合わせ最適化問題の近似解を多項式アルゴリズムで求める
• 近似アルゴリズムの精度
• 近似解が実行可能であることの考察

ちなみにコースを提供しているENS（École normale supérieure; 高等師範学校）というのはフランスの大学らしい。

　第1週は Vertex Cover を解くための Linear Programming RelaxationとRoundingについてだった。さっき課題を提出したが、記述式の問題で、生徒同士で評価しあう形式だった。数式を書かないといけないのでひさびさにlatexを使って学生に戻った気分になった。

　組み合わせ最適化問題は実世界の問題にも適用できる場面が多いので、基本を抑えてエンジニアとしての引き出しを増やしておきたい。