MAX-SAT approximation factor

Question

I am stuck on an exercise that ask the approximation factor of a MAX-SAT approximated algorithm generalized from a MAX-3SAT algorithm

MAX-3SAT:

1. set every variable with a random value ($0$ or $1$ each with probability $\frac12$)

2. check how many clauses are satisfied

This algorithm has a $\frac78$-approximation factor since:

• to get all $3$ variable to false we have a $\frac1{2^3}$ probability

• to get all $3$ variable true we have a $1 - \frac1{2^3}$ probability (since a clause to be satisfied need at least 1 variable true)

Now I am confused about the generalization to MAX-SAT Since we have N variables i'm inclined towards a $\left(1 - \frac1{2^N}\right)$-approximation factor since

• to satisfy the clauses we have a $\frac1{2^N}$ probability

• to negate the clauses we have a $1 - \frac1{2^N}$ probability

However, I'm not sure about that since in a SAT problem there is no guarantee that all clauses will have exactly $N$ variables since $N$ here represent only an upper bound on the number of variable per clause.

Answer 1

You are right in your analysis: this algorithm has a $\left(1-\frac{1}{2^N}\right)$ approximation factor only when each clause has at least $N$ independant litterals (independant means on different variables).

In the general case, you could have some clauses with exactly one litteral. But that means that the approximation factor is at least expected to be $\frac12$. However, since the algorithm is randomized, it cannot guarantee to get at least half of the clauses to be satisfied.

One interesting fact is that this algorithm can be derandomized to guarantee a $\geqslant \frac12$ approximation factor (the idea is to choose each assignation of a variable to maximize the expected approximation factor).