Uniform Random Assignment for MaxE4SAT

Definition

Uniform Random Assignment for MaxE4SAT

For MaxE4SAT, assign each variable true or false independently with probability $1/2$. Return the assignment. If $X$ is the number of satisfied clauses and there are $m$ clauses, then
$\mathbb{E}[X]=\frac{15}{16}m\ge \frac{15}{16}\mathrm{OPT}.$
This is an expected approximation guarantee, not a guarantee for every run.

Algorithm

for each variable x:
    independently choose sigma[x] uniformly from {false,true}
return sigma

Sampling takes $O(n)$ random bits and operations; evaluating the returned assignment takes $O(n+m)$ time for four-literal clauses.

One clause, sixteen equally likely patterns

Count the unique falsifying pattern

A clause has four literals on distinct variables. Their truth values are independent fair bits, whether the literals are positive or negative. There are $2^4=16$ equally likely patterns.

The clause fails precisely when all four literal values are false. Hence $\mathrm{Pr}[C_j\text{ false}]=1/16$ and $\mathrm{Pr}[C_j\text{ true}]=15/16$. The distinct-variable assumption matters: $(x\vee x\vee x\vee x)$ would be satisfied with probability only $1/2$.

Expected guarantee

Sum indicators, not independence assumptions about clauses

Represent each clause's contribution

Set $X_j=1[\sigma \models C_j]$. Then $X={\sum }_{j=1}^m{X}_j$ and $\mathbb{E}[X_j]=\mathrm{Pr}[X_j=1]=15/16$.

Apply linearity of expectation

$\mathbb{E}[X]={\sum }_{j=1}^m\mathbb{E}[X_j]=\frac{15m}{16}.$
Clauses may share variables, so their satisfaction events need not be independent. Linearity of expectation does not require that independence.

Compare with the optimum

No assignment satisfies more than all $m$ clauses, so $\mathrm{OPT}\le m$. Thus $\mathbb{E}[X]\ge (15/16)\mathrm{OPT}$.

At least one assignment satisfies at least $15m/16$ clauses: otherwise their average would be smaller. The sampling algorithm need not return such an assignment on every run.