论文标题
关于Max Nae-Sat的奥秘
On the Mysteries of MAX NAE-SAT
论文作者
论文摘要
Max Nae-SAT是一个自然优化问题，与其知名的相对最大SAT密切相关。如果所有子句具有相同的$ k $，则几乎完全了解了最大NAE-SAT的近似性状态，对于某些$ k \ ge 2 $。我们将此问题称为Max Nae-$ \ {K \} $ - SAT。对于$ k = 2 $，从本质上讲，这是著名的最大切割问题。对于$ k = 3 $，它与三角形可以分数覆盖的图表中的最大切割问题有关。对于$ k \ ge 4 $，众所周知，通过选择随机分配获得的近似值为$ 1- \ frac {1} {2^{k-1}} $，假设$ p \ ne np $是最佳的。对于每一个$ k \ ge 2 $，对于Max Nae-$ \ {K \} $ - SAT，可以获得至少$ \ frac {7} {8} $的近似值。因此，人们希望也有一个$ \ frac {7} {8} $ - Max Nae-Sat的近似算法，其中允许所有尺寸的条款同时同时使用。 我们的主要结果是没有$ \ frac {7} {8} $ - Max Nae-Sat的近似算法，假设有唯一的游戏猜想（UGC）。实际上，即使对于几乎令人满意的实例，最大nae-$ \ {3,5 \} $ - sat（即Max Nae-sat，所有条款的大小$ 3 $或$ 5 $），这是可以实现的最佳近似值，假设UGC，假设UGC，则最多是$ \ frac {3（3（\ sqrt）{3（\ sqrt {21} $}}}}。使用变体的计算，我们将O'Donnell和Wu的分析扩展到Max Nae-$ \ {3 \} $ - SAT。假设Max Nae-$ \ {3 \} $ - SAT，我们获得了最佳算法，假设UGC，则在先前的算法上有所改进。新算法的近似值为$ \ about 0.9089 $。 我们通过一些实验结果来补充理论结果。我们描述了一种近似算法，用于几乎令人满意的Max Nae-$ \ {3,5 \} $ - SAT-SAT以0.8728的猜想近似值为0.8728，而近似值算法几乎是可满足的Max Naee-Sat的近似值，并以猜测近似值为0.8698。
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 $k\ge 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 $k\ge 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\ne NP$. For every $k\ge 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 O'Donnell 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.
