Sums of squares based approximation algorithms for MAX-SAT

DOI10.1016/j.dam.2007.08.036zbMath1152.68058OpenAlexW2046077540MaRDI QIDQ944728

Hans van Maaren, Linda van Norden, Marijn J. H. Heule

Publication date: 10 September 2008

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

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

zbMATH Keywords

sums of squaressemidefinite programmingapproximation algorithmsmaximum satisfiability

Mathematics Subject Classification ID

Semidefinite programming (90C22) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (2)

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

Uses Software

• CSDP
• SDPA
• MAX-2-SAT
• SeDuMi
• COL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Semidefinite programming relaxations for semialgebraic problems
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• An improved semidefinite programming relaxation for the satisfiability problem
• On semidefinite programming relaxations for the satisfiability problem
• There are significantly more nonnegative polynomials than sums of squares
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• CSDP, A C library for semidefinite programming
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Some optimal inapproximability results

This page was built for publication: Sums of squares based approximation algorithms for MAX-SAT