On Semidefinite Programming Relaxations of (2+p)-SAT |
| |
Authors: | E de Klerk H van Maaren |
| |
Affiliation: | (1) Faculty of Information Technology and Systems, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands |
| |
Abstract: | Recently, de Klerk, van Maaren and Warners 10] investigated a relaxation of 3-SAT via semidefinite programming. Thus a 3-SAT formula is relaxed to a semidefinite feasibility problem. If the feasibility problem is infeasible then a certificate of unsatisfiability of the formula is obtained. The authors proved that this approach is exact for several polynomially solvable classes of logical formulae, including 2-SAT, pigeonhole formulae and mutilated chessboard formulae. In this paper we further explore this approach, and investigate the strength of the relaxation on (2+p)-SAT formulae, i.e., formulae with a fraction p of 3-clauses and a fraction (1–p) of 2-clauses. In the first instance, we provide an empirical computational evaluation of our approach. Secondly, we establish approximation guarantees of randomized and deterministic rounding schemes when the semidefinite feasibility problem is feasible, and also present computational results for the rounding schemes. In particular, we do a numerical and theoretical comparison of this relaxation and the stronger relaxation by Karloff and Zwick 15]. |
| |
Keywords: | approximation algorithms satisfiability semidefinite programming randomized rounding |
本文献已被 SpringerLink 等数据库收录! |
|