On semidefinite least squares and minimal unsatisfiability

DOI10.1016/J.DAM.2016.09.008MaRDI QIDQ516798zbMATHOpenAlexFDO

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

zbMATH Keywords

semidefinite programmingsatisfiabilityFarkas' lemmaminimal unsatisfiabilitysemidefinite least squares

Mathematics Subject Classification ID

Semidefinite programming (90C22)

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

Cites work

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

Cited in

(3)

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

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)