13.3.1.3. Combining the Two

The algorithm in Section 13.3.1.1 performs well for formulas with only large clauses but provides only a \(\frac12\)-approximation in general. The algorithm in Section 13.3.1.2 performs well for formulas with only small clauses but provides only a \(\bigl(1 - \frac{1}{e}\bigr)\)-approximation in general, that is, roughly a \(0.63\)-approximation. We can obtain an algorithm that combines the strengths of these two algorithms by picking one of them at random.

Specifically, we flip a fair coin. If it comes up heads, we run the first algorithm and report its answer. If the coin comes up tails, we run the second algorithm and report its answer. Let \(\hat x\) once again be the truth assignment reported by this algorithm and let \(\hat W\) be the total weight of the clauses satisfied by \(\hat x\).

Lemma 13.17: \(E\bigl[\hat W\bigr] \ge \frac34 \cdot \mathrm{OPT}\).

Proof: Consider a random variable \(b\) that is \(0\) if the coin comes up heads and \(1\) if the coin comes up tails. Then

\[E\bigl[\hat W_j\bigr] = \frac12 \cdot E\bigl[\hat W_j \mid b = 0\bigr] + \frac12 \cdot E\bigl[\hat W_j \mid b = 1\bigr].\]

By Lemmas 13.13 and 13.15, we have

\[E\bigl[\hat W_j \mid b = 0\bigr] \ge (1 - 2^{-s_j}) \cdot w_{C_j}\]

and

\[E\bigl[\hat W_j \mid b = 1\bigr] \ge \left[1 - \left(1 - \frac{1}{s_j}\right)^{s_j}\right] \cdot w_{C_j}\hat z_j,\]

where \(s_j\) is the size of clause \(C_j\) and \(\bigl(\hat y, \hat z\bigr)\) is the optimal solution of the LP relaxation of (13.13) used as the basis for rounding if we use the algorithm from Section 13.3.1.2. Since \(\hat z_j \le 1\), the first inequality implies that

\[E\bigl[\hat W_j \mid b = 0\bigr] \ge (1 - 2^{-s_j}) \cdot w_{C_j}\hat z_j.\]

Thus,

\[E\bigl[\hat W_j\bigr] \ge w_{C_j}\hat z_j \cdot \frac12 \left[ 1 - 2^{-s_j} + 1 - \left(1 - \frac{1}{s_j}\right)^{s_j} \right]\]

For \(s_j \in \{1, 2\}\), it is easy to verify that

\[1 - 2^{-s_j} + 1 - \left(1 - \frac{1}{s_j}\right)^{s_j} = \frac{3}{2}.\]

For \(s_j \ge 3\), we have

\[1 - 2^{-s_j} + 1 - \left(1 - \frac{1}{s_j}\right)^{s_j} \ge \frac{7}{8} + 1 - \frac{1}{e} > \frac{3}{2}.\]

Thus, \(E\bigl[\hat W_j\bigr] \ge \frac{3}{4} \cdot w_{C_j}\hat z_j\) and

\[E\bigl[\hat W\bigr] = \sum_{j=1}^m E\bigl[\hat W_j\bigr] \ge \frac{3}{4} \cdot \sum_{j=1}^m w_{C_j}\hat z_j = \frac{3}{4} \cdot \mathrm{OPT}_f \ge \frac{3}{4} \cdot \mathrm{OPT}.\ \text{▨}\]