Definition
Maximum Satisfiability Problem
The maximum SAT problem is a an optimisation problem variant of SAT that aims to maximise the number of satisfied clauses.
The optimisation problem is NP-hard; its threshold decision version is NP-complete.
Approximation
The best-of-two algorithm combines uniform random assignment with LP-guided randomised rounding. It satisfies at least of the optimum number of clauses in expectation and can be derandomised.