Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
复制标题
全局基数约束使得近似某些 Max-2-CSP 变得更加困难
DOI：
10.4230/lipics.approx-random.2019.24
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Stankovic
中科院分区：
文献类型：
--
作者：
Per Austrin;A. Stankovic
假设博弈猜想是唯一的，我们证明了一些带基数约束的布尔Max-2-CSP的现有逼近算法是最优的。特别地，我们证明了具有基数约束的最大割在\约0.858以内是UG-困难逼近的，具有基数约束的最大-2-Sat在\大约0.929内是UG-困难逼近的。在这两种情况下，先前的最佳硬度结果与相应的无约束MAX-2-CSP的硬度相同(MAX-CUT约为0.878，MAX-2-SAT约为0.940)。Max-2-Sat的难度适用于单调Max-2-Sat实例，这意味着我们也获得了Max-k-Vertex-Cover问题的紧不可逼近性。
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within \approx 0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within \approx 0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (\approx 0.878 for Max-Cut, and \approx 0.940 for Max-2-Sat). The hardness for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem.
DOI：
10.1145/3055399.3055412
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pasin Manurangsi
通讯作者：
Pasin Manurangsi