Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems
Miguel F. Anjos (anjosstanfordalumni.org)
Abstract: Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The approaches presented in some detail include the ground-breaking approximation algorithm of Goemans and Williamson for MAX-2-SAT, the Gap relaxation of de Klerk, van Maaren and Warners, and strengthenings of the Gap relaxation based on the Lasserre hierarchy of semidefinite liftings for polynomial optimization problems. We include theoretical and computational comparisons of the aforementioned semidefinite relaxations for the special case of 3-SAT, and conclude with a review of the most recent results in the application of semidefinite programming to SAT and MAX-SAT.
Keywords: satisfiability, maximum-satisfiability, semidefinite programming,semidefinite optimization, approximation algorithms, semidefinite relaxations,lifting procedures.
Category 1: Linear, Cone and Semidefinite Programming
Category 2: Combinatorial Optimization
Citation: Journal on Satisfiability, Boolean Modeling and Computation, Vol. 1, 2005, 1-47. http://www.isa.ewi.tudelft.nl/Jsat/
Entry Submitted: 09/08/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|