We have studied a 1/2 approximation for MAXSAT that executes in the expected polynomial time, randomly assigning each variable to True / False and repeating until it is obtained. an assignment with at least half of the clauses satisfied.
I do not understand why the algorithm has to be so complicated. Why does the following not give an approximation 1/2 of the MAXSAT in guaranteed linear time?
- Let $ m $ the number of clauses in the formula.
- Set all variables to true. Count the number of clauses satisfied. If it is at least $ m / $ 2 then return this assignment.
- Set all variables to false. Return this assignment.
Each clause contains at least one literal that will be satisfied by setting a variable to true or a variable to false. Thus, both missions satisfy at least a total of $ m $ clauses so that at least one of them satisfies $ ge m / $ 2 clauses.