On randomizing two derandomized greedy algorithms - 昏論会ウィキ

On randomizing two derandomized greedy algorithms

http://www.intlpress.com/JOC/JOC-vol-1.php

• MAX-SAT の有名な簡単なgreedy近似アルゴリズムは編集の順番をランダムに並び替えるだけの簡単なお仕事で近似値比(の期待値)が から where にあがる。
• MAX-CUT の有名な簡単なgreedy近似アルゴリズムは、同じ事をやっても のまま変わらない

前提知識

「(x1 | !x2) & (!x1) & (x2 | x3 | x4) みたいに内側から !、|、& の順に作ったブール論理式があります。これがtrueになるように頑張って変数の値を決めて下さい」という問題は SAT と呼ばれていますが、

「全体をtrueにするのは無理かも知れないので、...&...&... の & で繋いだ節のうちtrueになる数が最大になるように変数の値を決めて下さい」は MAX-SAT と言います。

「無理かも知れないので」と気遣ってくれる優しいふりをしていますが、MAX-SATの方が難しい問題です。騙されないで下さい。

難しいので近似アルゴリズムを考えます。最大じゃなくてもいいから、割とtrueになるのが多くなるように頑張ります。

「最適解の 2/3 まではtrueにできる」アルゴリズム。

• まず x1 を決める。「x1 を true/false にした後、残り全部をランダムに50%50%の確率で決めたときの期待値が大きい方」に決める。
• これで x1 は固定。
• 同様に、x2 も「x1 を true/false にした後、残り全部をランダムに50%50%の確率で決めたときの期待値が大きい方」に決める。
• 以下繰り返し。

オリジナルの提案論文ではわかっていなかった程度に複雑な解析を頑張ると2/3が言える。

内容

たぶんみなさんご存じの「ないーぶなクイックソートは最初からソートされてる入力に弱い」と似て、このアルゴリズムは、変数の順番をうまく選ぶと虐めることができて、それで虐めまくると実際に最悪の2/3になるデータが作れていることが知られている。

「じゃあ変数の順番ランダムに並べ替えてからこのアルゴリズム動かせば近似率よくなるんじゃね？？？？」

っていうのが長らくのopen problemだったのを、ちゃんと解析して、「近似率よくなる」と肯定的に示したのがこの論文。

証明は、元々の2/3の証明での不変条件式をδずつずらしたものもRandomizeすれば満たせる、というのをひたすら頑張っている…のだと思う…。（読めてない）