Semidefinite Programming Approaches for MAX-2-SAT and MAX-3-SAT: Computational Perspectives.

摘要

Semidefinite programming (SDP) relaxations - in conjunction with randomized rounding schemes -yield 7/8 and 0.931 approximation algorithms for MAX-3-SAT and MAX-2-SAT respectively. In spite of these powerful theoretical results, it is not clear if SDP can be used as a practical tool for solving MAX-SAT problems to optimality. In this regard, the usefulness of the SDP approach will ultimately depend on the ability to exploit sparsity in the SDP relaxations of large dimension. (The dimension corresponds to the number of variables and the sparsity is related to the number of clauses.) The authors present an investigation of sparsity issues for the SDP relaxations of Goemans and Williamson, and Feige and Goemans for MAX-2-SAT. Moreover, the authors test a branch and cut procedure to solve MAX-2-SAT to optimality, where the dual of the SDP relaxation is solved by interior point methods in order to exploit sparsity.