Sums of squares based approximation algorithms for MAX-SAT
type: Item
instance of: scholarly article
title: Sums of squares based approximation algorithms for MAX-SAT
zbMATH Open document ID: 1152.68058
published in: Discrete Applied Mathematics
publication date: 2008-09-10T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 5324149
zbMATH Keywords: maximum satisfiability
zbMATH Keywords: semidefinite programming
zbMATH Keywords: sums of squares
zbMATH Keywords: approximation algorithms
author: Hans van Maaren
author: Linda van Norden
author: Marijn J. H. Heule
describes a project that uses: CSDP
describes a project that uses: SDPA
describes a project that uses: SeDuMi
describes a project that uses: COL
describes a project that uses: MAX-2-SAT
MaRDI profile type: Publication
full work available at URL: j.dam.2007.08.036
OpenAlex ID: W2046077540
cites work: On semidefinite programming relaxations for the satisfiability problem
cites work: An improved semidefinite programming relaxation for the satisfiability problem
cites work: Q3429015
cites work: Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
cites work: There are significantly more nonnegative polynomials than sums of squares
cites work: CSDP, A C library for semidefinite programming
cites work: A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
cites work: Aspects of semidefinite programming. Interior point algorithms and selected applications
cites work: Q4550772
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Some optimal inapproximability results
cites work: Q5585021
cites work: Q4737518
cites work: Semidefinite programming relaxations for semialgebraic problems
cites work: Q4285035
cites work: Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
cites work: Q4828974
DOI: 10.1016/J.DAM.2007.08.036
Recommended article: Q4229151
Recommended article: Q4524463
Recommended article: On Some Recent Approximation Algorithms for MAX SAT
Recommended article: Q3129924
Recommended article: Approximation algorithms for the maximum satisfiability problem
Recommended article: Q4247437
Recommended article: Improved approximation algorithms for MAX SAT
Recommended article: Q4952605
Recommended article: Approximating MAX SAT by moderately exponential and parameterized algorithms
description: scientific article; zbMATH DE number 5324149