No label defined (Q4550772)

Semidefinite programming (SDF) 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 authors present an investigation of sparsity issues for the SPD relaxations of Goemans and Williamson, and Feige and Goemans for MAX-2-SAT. Moreover, they 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. Based on this numerical experience, the authors discuss possible extensions to MAX-3-SAT using the 7/8 relaxation of Karlow and Zwick for MAX-3-SAT. For the entire collection see [Zbl 0988.00046].