# satisfiability – MAXSAT approximation – Computer Science Stack Exchange

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.