Bounds and fast approximation algorithms for binary quadratic optimization problems with application to MAX 2SAT.
Hans van MaarenJoost P. WarnersPublished in: Discret. Appl. Math. (2000)
Keyphrases
- approximation algorithms
- max sat
- worst case
- lower bound
- np hard
- exact algorithms
- randomized algorithms
- upper bound
- special case
- constant factor
- branch and bound algorithm
- primal dual
- lower and upper bounds
- sat solvers
- vertex cover
- weighted max sat
- quadratic optimization problems
- approximation guarantees
- tabu search
- branch and bound