Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems

作     者：Anjos, Miguel F. 

作者机构：Department of Management Sciences Faculty of Engineering University of Waterloo Waterloo Ontario Canada N2L 3G1. E-mail: 

出 版 物：《Journal on Satisfiability, Boolean Modeling and Computation》 

年 卷 期：2005年第1卷第1期

页      面：1-47页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：satisfiability maximum-satisfiability semidefinite programming semidefinite optimization approximation algorithms semidefinite relaxations lifting procedures 

摘      要：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.