单选题：In the maximum satisfiability problem (MAX SAT), the input consi
In the maximum satisfiability problem (MAX SAT), the input consists of $$n$$ Boolean variables $$x_1,\ldots,x_n$$, $$m$$ clauses $$C_1,\ldots,C_m$$(each of which consists of a disjunction(that is an “or”) of some number of the variables and their negations, e.g. $$x_3 \vee \bar{x}_5 \vee x_{11}$$, where $$\bar{x}_i$$ is the negation of $$x_i$$), and a nonnegative weight $$w_j$$ for each clause $$C_j$$. The objective of the problem is to find an assignment of the true/false to the $$x_i$$ that maximizes the weight of the satisfied clauses.
A variable or a negated variable is a literal. The number of literals in a clause is called its length. Denote $$l_j$$ to be the length of a clause $$C_j$$ . Clauses of length 1 are called unit clauses.
**Randomized algorithm RA**: Setting each $$x_i$$ to true with probability $$p$$ independently.
Which of the following statement is false?
@[B](3)
A. Let $$p=1/2$$, the randomized algorithm RA is a $$2$$-approximation algorithm.
B. If $$l_j \geq 3$$ for each clause $$C_j$$. Let $$p=1/2$$, the randomized algorithm RA is a 9/8-approximation algorithm.
C. If MAX SAT instances do not have unit clauses $$\bar{x}_i$$, we can obtain a randomized $$ \frac{2}{\sqrt{5}-1} \approx 1.618$$-approximation algorithm for MAX SAT.
D. One could obtain a better bound on optimal solution than $$\sum_{j=1}^m w_j$$ for MAX SAT.
A.Let $$p=1/2$$, the randomized algorithm RA is a $$2$$-approximation algorithm.
B.If $$l_j \geq 3$$ for each clause $$C_j$$. Let $$p=1/2$$, the randomized algorithm RA is a 9/8-approximation algorithm.
C.If MAX SAT instances do not have unit clauses $$\bar{x}_i$$, we can obtain a randomized $$ \frac{2}{\sqrt{5}-1} \approx 1.618$$-approximation algorithm for MAX SAT.
D.One could obtain a better bound on optimal solution than $$\sum_{j=1}^m w_j$$ for MAX SAT.
答案：B
A variable or a negated variable is a literal. The number of literals in a clause is called its length. Denote $$l_j$$ to be the length of a clause $$C_j$$ . Clauses of length 1 are called unit clauses.
**Randomized algorithm RA**: Setting each $$x_i$$ to true with probability $$p$$ independently.
Which of the following statement is false?
@[B](3)
A. Let $$p=1/2$$, the randomized algorithm RA is a $$2$$-approximation algorithm.
B. If $$l_j \geq 3$$ for each clause $$C_j$$. Let $$p=1/2$$, the randomized algorithm RA is a 9/8-approximation algorithm.
C. If MAX SAT instances do not have unit clauses $$\bar{x}_i$$, we can obtain a randomized $$ \frac{2}{\sqrt{5}-1} \approx 1.618$$-approximation algorithm for MAX SAT.
D. One could obtain a better bound on optimal solution than $$\sum_{j=1}^m w_j$$ for MAX SAT.
A.Let $$p=1/2$$, the randomized algorithm RA is a $$2$$-approximation algorithm.
B.If $$l_j \geq 3$$ for each clause $$C_j$$. Let $$p=1/2$$, the randomized algorithm RA is a 9/8-approximation algorithm.
C.If MAX SAT instances do not have unit clauses $$\bar{x}_i$$, we can obtain a randomized $$ \frac{2}{\sqrt{5}-1} \approx 1.618$$-approximation algorithm for MAX SAT.
D.One could obtain a better bound on optimal solution than $$\sum_{j=1}^m w_j$$ for MAX SAT.
答案：B