13.3.1. A Randomized Monte Carlo Algorithm for MAX-SAT

We start with two very simple Monte Carlo algorithms for the MAX-SAT problem. One produces a good approximation for small clauses, the other shines for large clauses. We will show that a randomized combination of the two algorithms produces a truth assignment that satisfies clauses with expected total weight at least \(\frac34 \cdot \mathrm{OPT}\). In the next section, we show how to convert these algorithms into deterministic ones using the technique of conditional expectations.