On semidefinite programming relaxations of \((2+p)\)-SAT

DOI10.1023/A:1021208315170zbMath1050.68050MaRDI QIDQ1861907

Hans van Maaren, Etienne de Klerk

Publication date: 10 March 2003

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

semidefinite programmingsatisfiabilityapproximation algorithmsrandomized rounding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (5)

An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ On semidefinite least squares and minimal unsatisfiability ⋮ An improved semidefinite programming relaxation for the satisfiability problem ⋮ Semidefinite Programming and Constraint Programming

Uses Software

• SeDuMi

This page was built for publication: On semidefinite programming relaxations of \((2+p)\)-SAT