Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

DOI10.1016/J.DAM.2013.06.021zbMath1288.90059OpenAlexW2012205236MaRDI QIDQ2446872

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)

Related Items (1)

On semidefinite least squares and minimal unsatisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Handbook on semidefinite, conic and polynomial optimization
• Sums of squares based approximation algorithms for MAX-SAT
• The intractability of resolution
• Some results and experiments in programming techniques for propositional logic
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An improved semidefinite programming relaxation for the satisfiability problem
• On semidefinite programming relaxations of \((2+p)\)-SAT
• Relaxations of the satisfiability problem using semidefinite programming
• On semidefinite programming relaxations for the satisfiability problem
• An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Introduction to Mathematics of Satisfiability
• Hard examples for resolution
• Theory and Applications of Satisfiability Testing
• Handbook of semidefinite programming. Theory, algorithms, and applications

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