On the Mysteries of MAX NAE-SAT
On the Mysteries of MAX NAE-SAT
复制标题
MAX NAE-SAT 之谜
DOI：
10.1137/1.9781611976465.30
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zwick, Uri
中科院分区：
文献类型：
--
作者：
Brakensiek, Joshua;Huang, Neng;Potechin, Aaron;Zwick, Uri
MAX NAE-SAT是一个自然的优化问题，与其更知名的相对MAX SAT密切相关。MAX NAE-SAT的可近似性状态几乎完全理解，如果所有子句具有相同的sizek，对于somek≥ 2。我们将此问题称为MAX NAE-{k}-SAT。Fork= 2，它本质上是著名的MAX CUT问题。Fork= 3，它与三角形可以分数覆盖的图中的MAX CUT问题有关。Fork≥ 4时，已知在P <$NP条件下，通过随机分配得到的逼近比是最优的.对于每个k ≥ 2，对于MAX NAE-{k}-SAT，可以获得至少7/8的近似比。因此，有一些希望，也有一个7/8-近似算法的MAX NAE-SAT，其中所有大小的子句被允许同时。我们的主要结果是，没有7/8-近似算法的MAX NAE-SAT，假设唯一的游戏猜想（UGC）。事实上，即使对于MAX NAE-{3，5}-SAT的几乎可满足的实例（即，MAX NAE-SAT，其中所有子句的大小为3或5），假设UGC，可以达到的最佳近似比至多为.使用变分法，我们将奥唐纳和吴的MAX CUT分析扩展到MAX NAE-{3}-SAT。我们得到了一个最佳的算法，假设UGC，为MAX NAE-{3}-SAT，略有改进以前的算法。新算法的逼近比为0.9089。这给出了对于每个k ≥ 2的MAX NAE-{k}-SAT的充分理解。有趣的是，这种优化算法所使用的舍入函数是一个积分方程的解。本文给出了MAX NAE-{3，5}-SAT的几乎可满足情形的近似算法，其近似比为0.8728，以及MAX NAE-SAT的几乎可满足情形的近似算法，其近似比为0.8698.我们进一步推测，这些基本上是最好的近似比，可以实现这些问题，假设UGC。有些令人惊讶的是，这些近似算法使用的舍入函数是仅假设值±1的非单调阶跃函数。
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 sizek, for somek≥ 2. We refer to this problem as MAX NAE-{k}-SAT. Fork= 2, it is essentially the celebrated MAX CUT problem. Fork= 3, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. Fork≥ 4, it is known that an approximation ratio of , obtained by choosing a random assignment, is optimal, assumingP≠NP. For everyk≥ 2, an approximation ratio of at least 7/8 can be obtained for MAX NAE-{k}-SAT. There was some hope, therefore, that there is also a 7/8-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously.Our main result is that there isno7/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 .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 ≈ 0.9089. This gives a full understanding of MAX NAE-{k}-SAT for everyk≥ 2. Interestingly, the rounding function used by this optimal algorithm is the solution of an integral equation.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. We further conjecture that these are essentially the best approximation ratios that can be achieved for these problems, assuming the UGC. Somewhat surprisingly, the rounding functions used by these approximation algorithms are non-monotone step functions that assume only the values ±1.
登录
查看更多内容
平衡最大 2-sat 可能不是最难的
DOI：
10.1145/1250790.1250818
发表时间：
2007
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Per Austrin
通讯作者：
Per Austrin
如何舍入任何 CSP
DOI：
10.1109/focs.2009.74
发表时间：
2009
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
P. Raghavendra;David Steurer
通讯作者：
David Steurer
DOI：
--
发表时间：
2018
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Aaron Potechin
通讯作者：
Aaron Potechin
用于最大切割的最佳 sdp 算法，以及同样最佳的长代码测试
DOI：
--
发表时间：
2008
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
R. O'Donnell;Yi Wu
通讯作者：
Yi Wu
DOI：
10.1006/jagm.2001.1202
发表时间：
2000-02
期刊：
J. Algorithms
影响因子：
--
作者：
Takao Asano;David P. Williamson
通讯作者：
Takao Asano;David P. Williamson