MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size $k$, for some $kge 2$. We refer to this problem as MAX NAE-${k}$-SAT. For $k=2$, it is essentially the celebrated MAX CUT problem. For $k=3$, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For $kge 4$, it is known that an approximation ratio of $1-frac{1}{2^{k-1}}$, obtained by choosing a random assignment, is optimal, assuming $P e NP$. For every $kge 2$, an approximation ratio of at least $frac{7}{8}$ can be obtained for MAX NAE-${k}$-SAT. There was some hope, therefore, that there is also a $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no $frac{7}{8}$-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-${3,5}$-SAT (i.e., MAX NAE-SAT where all clauses have size $3$ or $5$), the best approximation ratio that can be achieved, assuming UGC, is at most $frac{3(sqrt{21}-4)}{2}approx 0.8739$. Using calculus of variations, we extend the analysis of ODonnell and Wu for MAX CUT to MAX NAE-${3}$-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-${3}$-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is $approx 0.9089$. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-${3,5}$-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698.
Download