13.3.1.1. A Good Algorithm for Large Clauses

The first randomized algorithm is essentially trivial: We set each variable \(x_i\) to true with probability \(\frac{1}{2}\). Let \(\hat x\) be the resulting truth assignment, let \(\hat W\) be the weight of the clauses satisfied by \(\hat x\), and let \(\hat W_j\) be the contribution of the \(j\)th clause \(C_j\) to \(\hat W\). In other words, \(\hat W_j = w_{C_j}\) if \(\hat x\) satisfies \(C_j\), and \(\hat W_j = 0\) otherwise.

Lemma 13.13: If all clauses in \(F\) have size at least \(k\), then

\[E\bigl[\hat W\bigr] \ge \bigl(1 - 2^{-k}\bigr) \cdot \mathrm{OPT}.\]

Proof: Let \(C_1, \ldots, C_m\) be the clauses in \(F\) and let \(p_j\) be the probability that \(\hat x\) satisfies \(C_j\). Then

\[E\bigl[\hat W_j\bigr] = w_{C_j}p_j\]

and

\[E\bigl[\hat W\bigr] = \sum_{j=1}^m E\bigl[\hat W_j\bigr].\]

\(C_j\) is not satisfied if and only if all literals in \(C_j\) are false. Since each literal is false with probability \(\frac{1}{2}\) and \(C_j\) contains at least \(k\) literals, this happens with probability at most \(2^{-k}\). Thus,

\[p_j \ge 1 - 2^{-k}\]

for all \(1 \le j \le m\) and, therefore,

\[E\bigl[\hat W_j\bigr] \ge \left(1 - 2^{-k}\right) \cdot w_{C_j},\]

that is,

\[E\bigl[\hat W\bigr] \ge \left(1 - 2^{-k}\right) \cdot \sum_{j=1}^m w_{C_j}.\]

Since the optimal solution satisfies at most all clauses in \(F\), we have

\[\mathrm{OPT} \le \sum_{j=1}^m w_{C_j},\]

that is,

\[E\bigl[\hat W\bigr] \ge \bigl(1 - 2^{-k}\bigr) \cdot \mathrm{OPT}.\ \text{▨}\]

Corollary 13.14: For any formula \(F\), \(E\bigl[\hat W\bigr] \ge \frac12 \cdot \mathrm{OPT}\).

Proof: Since every clause in \(F\) contains at least one literal, this follows by setting \(k = 1\) in Lemma 13.13. ▨