On Some Recent MAX SAT Approximation Algorithms.
Matthias PoloczekDavid P. WilliamsonAnke van ZuylenPublished in: CoRR (2013)
Keyphrases
- approximation algorithms
- max sat
- exact algorithms
- np hard
- branch and bound algorithm
- special case
- lower bound
- weighted max sat
- sat solvers
- vertex cover
- worst case
- branch and bound
- search algorithm
- tabu search
- sat problem
- approximation ratio
- satisfiability problem
- upper bound
- constant factor
- disjoint paths
- linear programming
- optimal solution
- max sat solver
- evolutionary algorithm
- constant factor approximation
- maximum satisfiability
- computational complexity
- randomized algorithms
- constraint satisfaction
- scheduling problem
- integer programming
- greedy algorithm