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.