Maximum Satisfiability Problem

From GM-RKB
(Redirected from MAX-SAT)
Jump to navigation Jump to search

See: Boolean Satisfiability Problem, MAX-SAT, MaxSAT, MAX-2SAT, MAX-3SAT.



References

2011


2004

  • Cohen, Cooper, Jeavons. A complete characterization of complexity for boolean constraint optimization problems. CP 2004.

1994

  • Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994

1986

  • Mark Krentel. The Complexity of Optimization Problems. 1986. ACM.

1973

  • D. S. Johnson. (1973). “Approximation algorithms for combinatorial problems.” In: Proceedings of the fifth annual ACM symposium on Theory of computing.