A new upper bound for Max-2-SAT: A graph-theoretic approach.
Daniel Binkele-RaibleHenning FernauPublished in: J. Discrete Algorithms (2010)
Keyphrases
- max sat
- upper bound
- lower bound
- branch and bound algorithm
- branch and bound
- weighted max sat
- worst case
- stochastic local search
- boolean satisfiability
- randomly generated
- objective function
- sat solvers
- variable ordering
- tabu search
- np hard
- column generation
- search algorithm
- optimal solution
- unsatisfiable cores
- satisfiability problem
- maximum satisfiability
- max sat solver
- sat problem
- search strategies
- orders of magnitude