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を使って学生に戻った気分になった。

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