On semidefinite least squares and minimal unsatisfiability

DOI10.1016/J.DAM.2016.09.008zbMATH Open1364.90243OpenAlexW2521729967MaRDI QIDQ516798FDOQ516798

Authors: Miguel F. Anjos, Manuel V. C. Vieira 

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.09.008

Recommendations

• Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
• scientific article; zbMATH DE number 2159161
• scientific article; zbMATH DE number 6000615
• An improved semidefinite programming relaxation for the satisfiability problem
• Relaxations of the satisfiability problem using semidefinite programming

zbMATH Keywords

semidefinite programmingsatisfiabilityFarkas' lemmaminimal unsatisfiabilitysemidefinite least squares

Mathematics Subject Classification ID

Semidefinite programming (90C22)

Cites Work

• Title not available (Why is that?)
• A Spectral Bundle Method for Semidefinite Programming
• The complexity of facets resolved
• Algorithms for computing minimal unsatisfiable subsets of constraints
• Title not available (Why is that?)
• A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas
• Recognition of \(q\)-Horn formulae in linear time
• An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Theory and Applications of Satisfiability Testing
• Categorisation of Clauses in Conjunctive Normal Forms: Minimally Unsatisfiable Sub-clause-sets and the Lean Kernel
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Some results and experiments in programming techniques for propositional logic
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Handbook on semidefinite, conic and polynomial optimization
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• Title not available (Why is that?)
• Using local search to find MSSes and MUSes
• Tautologies and positive solvability of linear homogeneous systems
• A polynomial-time algorithm for reducing the number of variables in MAX SAT problem
• An improved semidefinite programming relaxation for the satisfiability problem
• On exact selection of minimally unsatisfiable subformulae
• On semidefinite programming relaxations of \((2+p)\)-SAT
• Relaxations of the satisfiability problem using semidefinite programming
• On semidefinite programming relaxations for the satisfiability problem
• Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
• An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
• Title not available (Why is that?)
• An extended semidefinite relaxation for satisfiability
• Classroom Note:An Elementary Proof of Farkas' Lemma
• Theory and Applications of Satisfiability Testing
• Sums of squares based approximation algorithms for MAX-SAT

Cited In (3)

• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Calibrating Least Squares Semidefinite Programming with Equality and Inequality Constraints

This page was built for publication: On semidefinite least squares and minimal unsatisfiability

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