Alteration (The Probabilistic Method, Chapter 3)

• 手法 Alteration
  • 期待値を使って計算量や解の大きさなどをバウンドする
  • 基本アイディア：期待値が T → T 以上（以下）のものが存在
  • ランダムに解生成 → ちゃんとした解になるように修正，というののバウンドを考える
• 例: maximum independent set
  1. 確率 p で頂点を選択
  2. 独立点集合になるように削除
  3. ……というのの大きさの期待値を求める
     • p を動かして最大化すると，|V|/d
• バリエーション: Sum of failure expectations
  • 例：hypergraph の 2-coloring 不可のグラフが作れる最小辺数 m(n)
  • 確率 p が，失敗のパターン２つ X1, X2 の発生個数の期待値を支配する
  • 失敗個数の期待値が <1 となれば，失敗が 0 個の可能性あり＝条件を満たす解が存在する．
  • 計算テク：birth time
    • 各頂点に birth time t を [0, 1] で一様に割り当てられ，その順で何かが起こると考える
    • t は連続量なので積分したりして計算が楽になって嬉しい