読者です 読者をやめる 読者になる 読者になる

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