An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs

DOI10.1007/S10472-006-9041-2zbMath1143.90024OpenAlexW1989224068MaRDI QIDQ2643148

Miguel F. Anjos

Publication date: 23 August 2007

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

Full work available at URL: https://doi.org/10.1007/s10472-006-9041-2

zbMATH Keywords

global optimizationsemidefinite programmingcombinatorial optimizationsatisfiability problemdiscrete optimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Boolean programming (90C09) Classical propositional logic (03B05)

Related Items (2)

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ On semidefinite least squares and minimal unsatisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semidefinite programming for discrete optimization and matrix completion problems
• Some results and experiments in programming techniques for propositional logic
• Recognition of \(q\)-Horn formulae in linear time
• Semidefinite programming relaxations for semialgebraic problems
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Geometry of semidefinite Max-Cut relaxations via matrix ranks
• 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
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On semidefinite programming relaxations for the satisfiability problem
• Global Optimization with Polynomials and the Problem of Moments
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Outline of an algorithm for integer solutions to linear programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Theory and Applications of Satisfiability Testing
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Complexity of Positivstellensatz proofs for the knapsack
• Complexity of Null- and Positivstellensatz proofs

This page was built for publication: An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs