Approximation Hardness of Short Symmetric Instances of MAX-3SAT.
Piotr BermanMarek KarpinskiAlex D. ScottPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- max sat
- maximum satisfiability
- weighted max sat
- stochastic local search
- max sat solver
- lower bound
- random instances
- phase transition
- random sat instances
- sat problem
- propositional satisfiability
- sat solvers
- branch and bound algorithm
- satisfiability problem
- graph coloring
- branch and bound
- boolean satisfiability
- sat instances
- randomly generated
- tabu search
- exact algorithms
- search algorithm
- inference rules
- combinatorial problems
- constraint satisfaction
- unsatisfiable cores
- linear programming
- np complete
- random sat
- variable ordering
- upper bound
- approximation algorithms
- cnf formula
- finding optimal solutions
- computational complexity
- boolean formula
- evolutionary algorithm
- search tree
- data structure