Improved approximations for max set splitting and max NAE SAT
type: Item
instance of: scholarly article
title: Improved approximations for max set splitting and max NAE SAT
zbMATH Open document ID: 1122.68154
author: Jiawei Zhang
author: Yinyu Ye
author: Qiaoming Han
published in: Discrete Applied Mathematics
publication date: 2004-08-19T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 2093414
zbMATH Keywords: Max-Set-Splitting
zbMATH Keywords: Max NAE SAT
zbMATH Keywords: Approximation algorithm
zbMATH Keywords: Semidefinite programming relaxation
describes a project that uses: Outward rotations
MaRDI profile type: Publication
full work available at URL: j.dam.2002.07.001
OpenAlex ID: W2008289509
cites work: Q2753920
cites work: Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: Q4247459
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Q2753735
cites work: An improved rounding method and semidefinite programming relaxation for graph partition
cites work: Some optimal inapproximability results
cites work: Approximability of maximum splitting of k-sets and some other Apx-complete problems
cites work: Q4063085
cites work: Semidefinite relaxation and nonconvex quadratic optimization
cites work: The hardness of approximation: Gap location
cites work: Gadgets, Approximation, and Linear Programming
cites work: A .699-approximation algorithm for Max-Bisection.
cites work: Q4250183
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
DOI: 10.1016/J.DAM.2002.07.001
description: scientific article; zbMATH DE number 2093414