Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT.
Adi AvidorIdo BerkovitchUri ZwickPublished in: WAOA (2005)
Keyphrases
- max sat
- approximation algorithms
- exact algorithms
- np hard
- sat solvers
- lower bound
- weighted max sat
- sat problem
- branch and bound algorithm
- satisfiability problem
- special case
- search algorithm
- stochastic local search
- branch and bound
- worst case
- tabu search
- boolean satisfiability
- vertex cover
- variable ordering
- propositional satisfiability
- constraint satisfaction
- constant factor
- approximation ratio
- upper bound
- unsatisfiable cores
- maximum satisfiability
- search space
- cnf formula
- linear programming
- max sat solver
- np complete
- random sat instances
- decision problems
- constraint satisfaction problems
- computational complexity