Statement
Max-Satisfiability Problem (Max-SAT problem)
Provided with a boolean function
in CNF with variables and clauses, where each variable only appears in a single literal in each clause. What is an assignment maximising the number of satisfied clauses?
Solutions
- Max-SAT random approximation algorithm
- Runs in
and achieves a -approximation.
- Runs in