Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems

zbMATH Open1194.90064MaRDI QIDQ3429015FDOQ3429015

Authors: Miguel F. Anjos 

Publication date: 30 March 2007

Recommendations

• scientific article; zbMATH DE number 6000615
• An improved semidefinite programming relaxation for the satisfiability problem
• On semidefinite programming relaxations for the satisfiability problem
• scientific article; zbMATH DE number 1795723
• scientific article; zbMATH DE number 2159161

zbMATH Keywords

approximation algorithmssemidefinite relaxationslifting procedures

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Cited In (12)

• Sums of squares based approximation algorithms for MAX-SAT
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Semidefinite relaxations for partitioning, assignment and ordering problems
• Empirical Properties of Optima in Free Semidefinite Programs
• Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
• Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
• Semidefinite programming based approaches to the break minimization problem
• Iterative and core-guided maxsat solving: a survey and assessment
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• On semidefinite least squares and minimal unsatisfiability
• Title not available (Why is that?)

Uses Software

• SATLIB
• MAX-2-SAT
• SDPT3

This page was built for publication: Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems

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