Uniform Random Assignment for MaxE4SAT

Definition

Uniform Random Assignment for MaxE4SAT

For MaxE4SAT, assign each variable true or false independently with probability . Return the assignment. If is the number of satisfied clauses and there are clauses, then

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 random bits and operations; evaluating the returned assignment takes 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 equally likely patterns.

The clause fails precisely when all four literal values are false. Hence and . The distinct-variable assumption matters: would be satisfied with probability only .

Expected guarantee

Sum indicators, not independence assumptions about clauses

Represent each clause's contribution

Set . Then and .

Apply linearity of expectation

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 clauses, so . Thus .

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