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 は面白かった。