An improved semidefinite programming relaxation for the satisfiability problem
From MaRDI portal
Publication:1774165
DOI10.1007/s10107-003-0495-2zbMath1059.90117OpenAlexW2074116126MaRDI QIDQ1774165
Publication date: 29 April 2005
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: http://e-archive.informatik.uni-koeln.de/439/2/zaik2002-439.pdf
Related Items (5)
An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Semidefinite resolution and exactness of semidefinite relaxations for satisfiability ⋮ Sums of squares based approximation algorithms for MAX-SAT ⋮ On semidefinite least squares and minimal unsatisfiability ⋮ Semidefinite Programming and Constraint Programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Semidefinite programming for discrete optimization and matrix completion problems
- Reflection-projection method for convex feasibility problems with an obtuse cone
- A two-phase algorithm for solving a class of hard satisfiability problems
- A spectral bundle method with bounds
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- 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
- On semidefinite programming relaxations of \((2+p)\)-SAT
- Elliptic approximations of propositional formulae
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Global Optimization with Polynomials and the Problem of Moments
- Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Outward rotations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- On the Shannon capacity of a graph
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- A class of logic problems solvable by linear programming
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Semidefinite Programming in the Space of Partial Positive Semidefinite Matrices
- PENNON: A code for convex nonlinear and semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- GloptiPoly
- Handbook of semidefinite programming. Theory, algorithms, and applications
This page was built for publication: An improved semidefinite programming relaxation for the satisfiability problem
