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 が,失敗のパターン2つ X1, X2 の発生個数の期待値を支配する
    • 失敗個数の期待値が <1 となれば,失敗が 0 個の可能性あり=条件を満たす解が存在する.
    • 計算テク:birth time
      • 各頂点に birth time t を [0, 1] で一様に割り当てられ,その順で何かが起こると考える
      • t は連続量なので積分したりして計算が楽になって嬉しい