Improved approximations for max set splitting and max NAE SAT

DOI10.1016/j.dam.2002.07.001zbMath1122.68154OpenAlexW2008289509MaRDI QIDQ1878408

Qiaoming Han, Yinyu Ye, Jia-Wei Zhang

Publication date: 19 August 2004

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

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

zbMATH Keywords

Approximation algorithmSemidefinite programming relaxationMax NAE SATMax-Set-Splitting

Mathematics Subject Classification ID

Semidefinite programming (90C22) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Approximation with a fixed number of solutions of some multiobjective maximization problems, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, Minimizing worst-case and average-case makespan over scenarios, Approximating Max NAE-\(k\)-SAT by anonymous local search, Inclusion/exclusion meets measure and conquer, On the gap between the quadratic integer programming problem and its semidefinite relaxation, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Simple probabilistic analysis to generalize bottleneck graph multi-partitioning

Uses Software

• Outward rotations

Cites Work

• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The hardness of approximation: Gap location
• Approximability of maximum splitting of k-sets and some other Apx-complete problems
• An improved rounding method and semidefinite programming relaxation for graph partition
• Outward rotations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Gadgets, Approximation, and Linear Programming
• Some optimal inapproximability results
• A .699-approximation algorithm for Max-Bisection.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item