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

Related Items (2)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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