Max-Satisfiability Problem
programming
Statement
Max-Satisfiability Problem (Max-SAT problem)
Provided with a boolean function $f$ in CNF with $n$ variables and $m$ 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 $O(nm)$ and achieves a $1/2$-approximation.