Question

(a) Consider Max 3-SAT: given an instance with m clauses each containing exactly 3 distinct literals, find the assignment that satisfies as many of them as possible. Come up with a simple randomized algorithm that will achieve an approximation factor of 7/8 in expectation. That is, if the optimal solution satisfies c clauses, your algorithm should produce an assignment that satisfies at least 7c/8 clauses in expectation. Hint: use linearity of expectation!

(b) Given a Max 3-SAT instance I, let OPTI denote the maximum fraction of clauses in I satisfied by any variable assignment. What is the smallest value of OPTI over all instances I ? In other words, what is minI OPTI ?


Hint: use part (a), and note that a random variable must sometimes be at least its mean.

Answer 1

(a) Use a simple randomized algorithm for Max 3-SAT that sets each variable independently to true with probability 1/2. Apply linearity of expectation to show that the expected fraction of satisfied clauses is 7/8 times the optimal.

(b) The smallest value of OPTI over all instances I is 7/8. This is achieved by the algorithm from part (a), where the expected fraction of satisfied clauses is 7/8 times the optimal. Thus, OPTI can be achieved with high probability, making 7/8 the minimum achievable value over all instances.

(a) To achieve an approximation factor of 7/8 in expectation for Max 3-SAT, we can use a simple randomized algorithm. Set each variable independently to true with probability 1/2 and false with probability 1/2. By doing this, we ensure that each clause is satisfied with a probability of at least 7/8.

To prove this, we use the linearity of expectation. Let X be the random variable representing the fraction of satisfied clauses. The expected value E[X] is the sum of the probabilities of satisfying each clause. Since each clause is satisfied with probability at least 7/8, we have E[X] ≥ 7/8. Therefore, the algorithm achieves an approximation factor of 7/8 in expectation.

(b) The smallest value of OPTI, denoting the maximum fraction of clauses satisfied by any variable assignment in a Max 3-SAT instance, is 7/8. This follows from the algorithm described in part (a), where each variable is independently set to true with probability 1/2.

Consider any instance I of Max 3-SAT, and let OPTI be the maximum fraction of clauses satisfied by any assignment. The algorithm's expected fraction of satisfied clauses is at least 7/8 times OPTI. As the algorithm's expected performance is 7/8 of the optimal, it implies that OPTI can be achieved with high probability.

To understand this, consider a random variable that represents the fraction of satisfied clauses. By the linearity of expectation, the expected value of this random variable is the sum of the probabilities of satisfying each clause. Since each clause is satisfied with probability at least 7/8, the overall expected fraction is also at least 7/8 times the optimal. Therefore, 7/8 is the smallest value of OPTI over all instances I.