13.3. Derandomization

Randomized algorithms are often more elegant and much simpler than deterministic algorithms for the same problem that achieve the same performance. Nevertheless, we would much prefer to have guarantee that the algorithm is fast and computes a correct output. Deterministic algorithms offer such guarantees. Randomized algorithms do not. Thus, a question studied extensively by some researchers is when it is possible to convert a randomized algorithm into a deterministic one without making its running time or, in the case of approximation algorithms, its approximation ratio much worse. An ideally, we would like to do this while maintaining the elegance of the randomized algorithm. This conversion of randomized algorithms into deterministic ones is called derandomization, because we remove the randomness from the algorithm.

We will not discuss derandomization in any detail in this course. However, a discussion of randomized LP rounding would not be complete without at least one example where the randomized rounding procedure can be converted into a deterministic one. The technique we use to achieve this conversion is called the method of conditional expectations, an elementary but important technique used to derandomize randomized algorithms. We illustrate this approach using the maximum satisfiability problem.

Recall the satisfiability problem (SAT): Given a Boolean formula in CNF

\[F = (\lambda_{1,1} \vee \cdots \vee \lambda_{1,s_1}) \wedge \cdots \wedge (\lambda_{m,1} \vee \cdots \vee \lambda_{m,s_m}),\]

decide whether there exists a truth assignment to the variables \(x_1, \ldots, x_n\) occurring in $F$ that satisfies \(F\), that is, that ensures that each clause contains at least one true literal. Each literal \(\lambda_{i,j}\) is a Boolean variable \(x_k\) or its negation \(\bar x_k\).

The answer may be no. In this case, we can ask what the maximum number of clauses is that any truth assignment can satisfy. If you think about the formula as modelling a set of constraints we try to satisfy, each represented by one of the clauses, it is not hard to imagine that some constraints are more important than others. For example, when scheduling classes on campus, making sure different classes taught by the same instructor are scheduled at different times is clearly more important than a personal preference not to teach after 5 p.m. We can model this by giving the clauses weights and asking which truth assignment satisfies a set of clauses of maximum weight.

Maximum Satisfiability (MAX-SAT) Problem: Given a Boolean formula \(F\) in CNF and a weight function \(w\) assigning weights to the clauses of \(F\), find a truth assignment that maximizes the total weight of all clauses in \(F\) satisfied by this truth assignment.

In contrast to SAT, which can be solved in polynomial time if all clauses have size \(2\) (contain two literals), MAX-SAT remains NP-hard even for this restricted case. Our goal in this section is to obtain a deterministic \(\frac34\)-approximation algorithm for MAX-SAT.