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

DOI10.1016/S0020-0190(98)00021-0zbMath1338.68286MaRDI QIDQ293272

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

linear programmingsemidefinite programmingapproximation algorithmsset splitting

Mathematics Subject Classification ID

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

Related Items (8)

Improved approximations for max set splitting and max NAE SAT ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Inclusion/exclusion meets measure and conquer ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Improved parameterized set splitting algorithms: A Probabilistic approach

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• The hardness of approximation: Gap location
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• Max NP-completeness made easy
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

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