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.

Contact: yinyu-ye@uiowa.edu


 [DVI]  [PS]  [IP PAGE]  [SEARCH AGAIN]