Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}

DOI10.1016/S0020-0190(98)00021-0MaRDI QIDQ293272zbMATH OpenFDO

Authors Gunnar Andersson, Lars Engebretsen

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098000210?np=y

zbMATH Keywords

approximation algorithmslinear programmingsemidefinite programmingset splitting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Linear programming (90C05) Semidefinite programming (90C22)

Recommendations

• Improved approximations for max set splitting and max NAE SAT
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Approximation and Online Algorithms
• scientific article; zbMATH DE number 1670538
• Improved approximation algorithms for MAX SAT

Cites work

• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• Approximation algorithms for combinatorial problems
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max NP-completeness made easy
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Optimization, approximation, and complexity classes
• The hardness of approximation: Gap location

Cited in

(17)

• Improved parameterized set splitting algorithms: A Probabilistic approach
• Improved approximations for max set splitting and max NAE SAT
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Inclusion/exclusion meets measure and conquer
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• On the Approximability of Splitting-SAT in 2-CNF Horn Formulas
• Local search to approximate MAX NAE-k-SAT tightly
• Approximating Max NAE-\(k\)-SAT by anonymous local search
• Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability
• A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
• Approximation algorithms on k-correlation clustering of uniform hypergraphs
• An improved approximation algorithm for hypergraph max p-section
• On the mysteries of MAX NAE-SAT
• A simple approximation algorithm for k-correlation clustering on uniform hypergraphs
• Separating \textsc{max} 2-and, \textsc{max di-cut}, and \textsc{max cut}
• An improved SDP rounding approximation algorithm for the max hypergraph bisection

This page was built for publication: Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}

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