On Some Recent Approximation Algorithms for MAX SAT.
Matthias PoloczekDavid P. WilliamsonAnke van ZuylenPublished in: LATIN (2014)
Keyphrases
- approximation algorithms
- max sat
- exact algorithms
- np hard
- special case
- branch and bound algorithm
- weighted max sat
- lower bound
- worst case
- search algorithm
- sat solvers
- sat problem
- vertex cover
- satisfiability problem
- branch and bound
- randomized algorithms
- primal dual
- np complete
- approximation ratio
- constant factor approximation
- tabu search
- boolean satisfiability
- linear programming
- disjoint paths
- upper bound
- constraint satisfaction
- constant factor
- maximum satisfiability
- neural network
- max sat solver
- integer programming