Question

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!

Answer 1

A simple randomized algorithm for Max 3-SAT achieves a 7/8 approximation factor in expectation. It assigns truth values randomly, repeats the process, and averages results, leveraging the linearity of expectation for reliable estimation.

To achieve an approximation factor of 7/8 in expectation for Max 3-SAT, you can use the following simple randomized algorithm:

1. Random Assignment:

Randomly assign truth values (True or False) to each variable with equal probability.

2. Count Satisfied Clauses:

Count the number of satisfied clauses based on the random assignment.

3. Repeat and Average:

Repeat the random assignment process multiple times (let's say k times), and calculate the average number of satisfied clauses.

4. Algorithm:

- For each iteration, assign truth values randomly to each variable.

- Count the number of satisfied clauses.

- Repeat this process k times and average the results.

5. Linearity of Expectation:

Due to the linearity of expectation, the expected number of satisfied clauses for each iteration is 7/8 of the total clauses (since each clause has a 7/8 chance of being satisfied).

6. Conclusion:

The algorithm achieves an approximation factor of 7/8 in expectation since, on average, it satisfies 7/8 of the clauses over multiple iterations.

This algorithm leverages the concept of linearity of expectation to estimate the expected performance over multiple runs, providing a reliable approximation for Max 3-SAT.