$\text{size}(c) = k$ とし, $\alpha _k = 1 - 2 ^ {-k}$ とする. このとき, $\mathrm{E}[W_c] = \alpha _k w_c$.
クローズ$c$ が満たされないのは, それに含まれるリテラルが全て偽であるときかつそのときのみ. そうなる確率は$2^{-k}$ であるから, 充足される確率は$1 - 2^{-k}$ である. $//$
アルゴリズム1 は$\dfrac{1}{2}$ 近似アルゴリズムである.
期待値の線形性と, $k \geq 1$ に対して$\alpha _k \geq \dfrac{1}{2}$ であるという事実から,
論理式$f$ の自己リダクション木$T$ の条件付き期待値も$\text{poly}(n)$で求まる.
(自己リダクション性・自己リダクション木についてはこちら を参照.)
ノード$x_1 = a_1, \cdots, x_i = a_i$ を考える. $\phi$ をこのノードに対して自己リダクションを行なって得られる変数$x_{i + 1}, \cdots, x_n$ のブール論理式であるとする. $x_{i + 1}, \cdots, x_n$ に対するランダム真偽割当に於ける$\phi$ の満たされるクローズの重みは明らかに$\text{poly}(n)$ で計算可能.
$x_1 = a_1, \cdots, x_n = a_n$ に対する部分的割当で既に満たされている$f$ のクローズの総コストを加える事で答えが得られる. $//$
根から葉へのパスで, パス上のノードはいずれも条件付き期待値が$\mathrm{E}[W]$ 以上となるものが$\text{poly}(n)$ で求まる.
ノードの条件付き期待値は, そのノードの2 つの子の条件付き期待値の平均で, 以下の式が成立する. $$ \mathrm{E}[W | x_1=a_1, \cdots, x_i = a_i] = \mathrm{E}[W | x_1 = a_1, \cdots, x_i = a_i, x_i+1 = \text{true}] / 2 + \mathrm{E}[W | x_1 = a_1, \cdots, x_i = a_i, x_i+1 = \text{false}] / 2 $$ これから, 条件付き期待値が大きい方の子は, 親の条件付き期待値以上になることが言える. これにより所望のパスの存在が確立され, 補題1.3 を用いてそのようなパスが多項式時間で求まることが保証される. $//$
$\beta _k = 1 - \left (1 - \dfrac{1}{k} \right )^k$ とする($k \geq 1$). このとき, $\text{size}(c) = k$ ならば$\mathrm{E}[W_c] \geq \beta _k w_c z_c^*$.
一般性を失うことなく, クローズ$c$ に現れるリテラルはすべて肯定形であると仮定できる. さらに変数名を入れ替えて$c = (x_1 \lor \cdots \lor x_k)$ と仮定できる. このクローズは$x_1, \cdots, x_k$ のすべてが偽でない限り満たされる. そのような事象が起こる確率は \begin{align*} \displaystyle 1 - \prod_{i=1}^{k}(1-y_i) & \geq 1 - \left ( \dfrac{\sum_{i = 1}^{k}(1 - y_i)}{k} \right )^k & [相加相乗平均]\\ & = 1 - \left (1 - \dfrac{\sum_{i = 1}^{k}y_i}{k} \right) ^k \\ & \geq 1 - \left (1 - \dfrac{z_c^*}{k} \right ) ^k & [\text{LP} の制約] \end{align*} ここで, 関数$g$ を$g(z) = 1 - \left(1 - \dfrac{z}{k} \right)^k$ とすると, $g$ は凹関数で$g(0) = 0, g(1) = \beta _k$ を満たす. よって, $z \in [0, 1]$ に対して$g(z) \geq \beta _k z$ が成立. したがって, $\mathrm{Pr}[c が満たされる] \geq \beta _k z_c^*$ が得られる. よって示したい命題が得られる. $//$
アルゴリズム2 は$1 - 1/e$ 近似アルゴリズムである.
$\text{OPT}_f$ をスライド中のLP 緩和を行なって得た最適解とすると, $$\displaystyle \mathrm{E}[W] = \sum_{c \in \mathcal{C}} \mathrm{E}[W_c] \geq \beta _k \sum_{c \in \mathcal{C}} w_cz_c^* = \beta _k \text{OPT}_f \geq \beta _k \text{OPT}$$ また, 任意の正整数$k$ について, $\left (1 - \dfrac{1}{k} \right )^k < \dfrac{1}{e}$. よってこのアルゴリズムはMAX-SAT に対する$1-\dfrac{1}{e}$ 近似アルゴリズムである. $//$
アルゴリズム1 を確率$\dfrac{1}{2}$, アルゴリズム2 を確率$\dfrac{1}{2}$ で実行するとき, $\mathrm{E}[W_c] \geq \dfrac{3}{4}w_cz_c^*$ となる.
$\text{size}(c) = k$ とする. 補題16.1 と, $z_c^* \leq 1 $ であることを用いると $$ \mathrm{E}[W_c | アルゴリズム1 を適用] = \alpha _k w_c \geq \alpha _k w_c z_c^* $$ 一方, 補題1.5 より $$ \mathrm{E}[W_c | アルゴリズム2 を適用] \geq \beta _k w_c z_c^* $$ 組み合わせると \begin{align*} \mathrm{E}[W_c] &= \dfrac{1}{2}(\mathrm{E}[W_c | アルゴリズム1 を適用] + \mathrm{E}[W_c | アルゴリズム2 を適用])\\ &= w_c z_c^* \dfrac{(\alpha _k + \beta _k)}{2} \end{align*} ここで, $\alpha _1 + \beta _1 = \alpha _2 + \beta _2 = \dfrac{3}{2}$, $k\geq3$ ならば$\alpha _k + \beta _k \geq \dfrac{7}{8} + 1 - \dfrac{1}{e} \geq \dfrac{3}{2}$. よって補題が得られる. $//$
アルゴリズム3 はMAX-SAT に対する$\dfrac{3}{4}$ の近似アルゴリズムである.
2 つの条件付き期待値$\mathrm{E}[W | \mathrm{アルゴリズム1 を適用}]$ と$\mathrm{E}[W | アルゴリズム2 を適用]$ のうちで, 1 つは$\mathrm{E}[W]$ 以上である. したがって, $\tau_1$ と$\tau_2$ のうち良い方で満たされるクローズのコストの総和は$\mathrm{E}[W]$ 以上である. $//$