Max-k-exact-satisfiability problem
programming
Statement
Max-$k$-exact-satisfiability 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 and each clause has exactly $k$ litterals. What is an assignment maximising the number of satisfied clauses?
Solutions
- Max-SAT random approximation algorithm
- Runs in $O(nm)$ time.
- Is an $(1-2^{-k})$-approximation algorithm.