Improved Approximation for Max Set Splitting and Max NAE SAT
Yang, Ye and Zhang
We present a $0.7499$-approximation algorithm for Max Set Splitting in
this paper. The previously best known result for this problem is a
$0.7240$-approximation due to Andersson and Engebretsen, which is
based on a semidefinite programming (SDP) relaxation. Our improvement
is resulted from a strengthened SDP relaxation, an improved rounding
method, and a tighter analysis.
Working Paper, Department of Management Sciences, The
University of Iowa, Iowa City, IA 52242, USA.