Max-k-exact-satisfiability problem

Statement

Max- -exact-satisfiability problem

Provided with a boolean function in CNF with variables and clauses, where each variable only appears in a single literal in each clause and each clause has exactly litterals. What is an assignment maximising the number of satisfied clauses?

Solutions

• Max-SAT random approximation algorithm
  • Runs in time.
  • Is an -approximation algorithm.

Theory

Related problems

• Max-SAT