An Introduction to Approximation Algorithms (Chapter 1, The Design of Approximation Algorithms)

Set Cover 問題をひたすら扱う

• Deterministic LP rounding
  • 要素の最大次数を f とする
  • LP を解き，1/f 以上になっているやつを 1 にする
  • f 近似
• Deterministic dual LP rounding
  • 相補性定理
  • Primal-dual を使うと簡単に Dual 解が求まる
• Greedy
  • 「コスト/新たにカバーできる要素数」が最大のものをとっていく
  • H_n 近似（タイト）
• Randomized LP rounding
  • 定数 c
  • 集合 j に対し，「確率 x^*_j で表が出るコイン」を c ln n 回振って，表が出たら採用
  • 確率 1/n^{c-1} でカバーされる
  • コストの期待値 c ln n
  • 「コスト | カバーされる」の期待値 2c ln n