Sums of squares based approximation algorithms for MAX-SAT

DOI10.1016/J.DAM.2007.08.036MaRDI QIDQ944728zbMATH OpenOpenAlexFDO

Authors 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

semidefinite programmingapproximation algorithmssums of squaresmaximum satisfiability

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1258327
• scientific article; zbMATH DE number 1552232
• On Some Recent Approximation Algorithms for MAX SAT
• scientific article; zbMATH DE number 1002206
• Approximation algorithms for the maximum satisfiability problem
• scientific article; zbMATH DE number 1302170
• Improved approximation algorithms for MAX SAT
• Publication:4952605
• Approximating MAX SAT by moderately exponential and parameterized algorithms

Cites work

• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• scientific article; zbMATH DE number 1795723 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 2119703 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• An improved semidefinite programming relaxation for the satisfiability problem
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• CSDP, A C library for semidefinite programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On semidefinite programming relaxations for the satisfiability problem
• Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
• Semidefinite programming relaxations for semialgebraic problems
• Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
• Some optimal inapproximability results
• There are significantly more nonnegative polynomials than sums of squares
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(8)

• Lower bounds of functions on finite abelian groups
• Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT
• Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1258327 (Why is no real title available?)
• On semidefinite least squares and minimal unsatisfiability
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
• scientific article; zbMATH DE number 1552232 (Why is no real title available?)

Describes a project that uses

Uses Software

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

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

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