13.3.2. A Deterministic Algorithm for MAX-SAT

The key to obtaining a deterministic \(\frac34\)-approximation algorithm for MAX-SAT is to derandomize the algorithms from Sections 13.3.1.1 and 13.3.1.2, that is, to obtain deterministic algorithms with the same approximation ratios.

Indeed, the algorithm from Section 13.3.1.3 satisfies

\[E\bigl[\hat W\bigr] = \frac12\Bigl(E\bigl[\tilde W\bigr] + E\bigl[\breve W\bigr]\Bigr),\]

that is,

\[\max\Bigl(E\bigl[\tilde W\bigr], E\bigl[\breve W\bigr]\Bigr) \ge E\bigl[\hat W\bigr] \ge \frac34 \cdot \mathrm{OPT},\]

where \(\tilde W\) is the solution computed by the algorithm from Section 13.3.1.1 and \(\breve W\) is the solution computed by the algorithm from Section 13.3.1.2.

Now assume that we have two deterministic algorithms \(\mathcal{A}_1\) and \(\mathcal{A}_2\) that, respectively compute solutions with guaranteed weight at least \(E\bigl[\tilde W\bigr]\) and \(E\bigl[\breve W\bigr]\), respectively. Then we can run both \(\mathcal{A}_1\) and \(\mathcal{A}_2\) and report the better of the two solutions computed by these algorithms. The solution produced by this algorithm has weight at least

\[\max\Bigl(E\bigl[\tilde W\bigr], E\bigl[\breve W\bigr]\Bigr) \ge \frac34 \cdot \mathrm{OPT},\]

that is, we obtain a deterministic \(\frac34\)-approximation algorithm.

Derandomizing the Algorithm for Large Clauses

Consider the algorithm for large clauses from Section 13.3.1.1 and let \((\tau_1, \ldots, \tau_k)\) be a Boolean vector, where \(0 \le k \le n\). Then \(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr]\) is the expected weight of the clauses satisfied by the truth assignment \(\hat x\) computed by the algorithm, provided the algorithm chooses \(\hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\) for the first \(k\) variables.

Note that \(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr]\) can be computed in polynomial time:

We split the clauses in \(F\) into three sets. \(F_s\) is the set of clauses satisfied by \(\bigl(\hat x_1, \ldots, \hat x_k\bigr)\). \(F_u\) is the set of clauses not satisfied by \(\bigl(\hat x_1, \ldots, \hat x_k\bigl)\) and not containing any variables not in \(\{x_1, \ldots, x_k\}\). \(F_? = F \setminus (F_s \cup F_u)\) is the set of all undecided clauses, that is, clauses that are not satisfied by \(\bigl(\hat x_1, \ldots, \hat x_k\bigr)\) but which can still be satisfied using appropriate choices of the values \(\hat x_{k+1}, \ldots, \hat x_n\).

For each clause \(C_j \in F_s\), we have

\[E\bigl[\hat W_j \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] = w_{C_j}\]

because \(C_j\) is satisfied no matter how we choose \(\hat x_{k+1}, \ldots, \hat x_n\). Similarly, each clause \(C_j \in F_u\) satisfies

\[E\bigl[\hat W_j \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] = 0\]

because \(C_j\) is not satisfied by \(\hat x_1, \ldots, \hat x_k\) and contains none of the variables \(\hat x_{k+1}, \ldots, \hat x_n\) that could be used to satisfy it. Analogously to the proof of Lemma 13.13, each clause \(C_j \in F_?\) satisfies

\[E\bigl[\hat W_j \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] = \left(1 - 2^{-s_j'}\right) \cdot w_{C_j},\]

where \(s_j'\) is the number of variables in \(\{x_{k+1}, \ldots, x_n\}\) that occur in \(C_j\). All these expectations can be computed in polynomial time.

Since

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] = \sum_{j=1}^m E\bigl[\hat W_j \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr],\]

we can thus compute \(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr]\) in polynomial time.

This allows us to implement the following deterministic MAX-SAT algorithm: We start with the empty truth assignment, that is, with \(k = 0\). In this case,

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] = E\bigl[\hat W\bigr].\]

As the algorithm progresses, it maintains the invariant that

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] \ge E\bigl[\hat W\bigr].\]

Once \(k = n\), we thus obtain a truth assignment \(\hat x = \tau\) that satisfies clauses of total weight at least \(E\bigl[\hat W\bigr]\).

So assume we have chosen values \(\tau_1, \ldots, \tau_k\) for \(\hat x_1, \ldots, \hat x_k\) so far and that

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] \ge E\bigl[\hat W\bigr].\]

We have

\[\begin{multline} E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] =\\ \frac12\Bigl(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{false}\bigr] +\\ E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{true}\bigr]\Bigr). \end{multline}\]

Since we can compute these conditional expectations in polynomial time, we can choose \(\tau_{k+1} \in \{\textrm{false}, \textrm{true}\}\) so that \(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_{k+1} = \tau_{k+1}\bigr]\) is maximized. This ensures that

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_{k+1} = \tau_{k+1}\bigr] \ge E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] \ge E\bigl[\hat W\bigr],\]

that is, the invariant is maintained.

Derandomizing the Algorithm for Small Clauses

The strategy is essentially identical to the strategy for the algorithm for large clauses. We observe that

\[\begin{multline} E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] =\\ \bigl(1 - \hat y_{k+1}\bigr) \cdot E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{false}\bigr] +\\ \hat y_{k+1} \cdot E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{true}\bigr] \end{multline}\]

because the algorithm sets \(\hat x_{k+1} = \textrm{true}\) with probability \(\hat y_{k+1}\). Thus, once again, we can choose \(\tau_{k+1}\) so that \(E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_{k+1} = \tau_{k+1}\bigr]\) is maximized to ensure that

\[E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_{k+1} = \tau_{k+1}\bigr] \ge E\bigl[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k\bigr] \ge E\bigl[\hat W\bigr].\]

This ensures that the final truth assignment \(\hat x = \tau\) satisfies clauses of total weight at least \(E\bigl[\hat W\bigr]\).

Note that we can once again compute the conditional expectations \(E[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{false}]\) and \(E[\hat W \mid \hat x_1 = \tau_1, \ldots, \hat x_k = \tau_k, \hat x_{k+1} = \textrm{true}]\) in polynomial time by dividing the clauses in \(F\) into three sets \(F_s\), \(F_u\), and \(F_?\) as above and calculating the probability of satisfying a clause in \(F_?\) as \(1 - \prod_{x_i \in C_j^+; i > k} \bigl(1 - \hat y_i\bigr) \cdot \prod_{x_i \in C_j^-; i > k} \hat y_i\).