Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

DOI10.1016/J.DAM.2013.06.021MaRDI QIDQ2446872zbMATH OpenOpenAlexFDO

Authors Miguel F. Anjos, Manuel V. C. Vieira

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.06.021

zbMATH Keywords

resolutionsatisfiabilitysemidefinite relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Recommendations

• An extended semidefinite relaxation for satisfiability
• On semidefinite programming relaxations for the satisfiability problem
• scientific article; zbMATH DE number 2159161
• An improved semidefinite programming relaxation for the satisfiability problem
• Relaxations of the satisfiability problem using semidefinite programming

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
• An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
• An extended semidefinite relaxation for satisfiability
• An improved semidefinite programming relaxation for the satisfiability problem
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Handbook on semidefinite, conic and polynomial optimization
• Hard examples for resolution
• scientific article; zbMATH DE number 1324220 (Why is no real title available?)
• scientific article; zbMATH DE number 2159161 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• Introduction to Mathematics of Satisfiability
• On semidefinite programming relaxations for the satisfiability problem
• On semidefinite programming relaxations of \((2+p)\)-SAT
• Relaxations of the satisfiability problem using semidefinite programming
• Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
• Semidefinite programming and integer programming
• Some results and experiments in programming techniques for propositional logic
• Sums of squares based approximation algorithms for MAX-SAT
• The intractability of resolution
• Theory and Applications of Satisfiability Testing

Cited in

(5)

• On semidefinite programming relaxations of \((2+p)\)-SAT
• Relaxations of the satisfiability problem using semidefinite programming
• scientific article; zbMATH DE number 6000615 (Why is no real title available?)
• scientific article; zbMATH DE number 2159161 (Why is no real title available?)
• On semidefinite least squares and minimal unsatisfiability

This page was built for publication: Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446872)