Complexity of Approximating CSP with Balance / Hard Constraints
Complexity of Approximating CSP with Balance / Hard Constraints
复制标题
具有平衡/硬约束的近似 CSP 的复杂性
DOI：
--
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
Euiwoong Lee
中科院分区：
文献类型：
--
作者：
V. Guruswami;Euiwoong Lee
我们研究了约束满足问题的两个自然推广。Balance-Max-CSP要求在任何可行的分配中，域中的每个元素都被使用相同的次数。Hard-Max-CSP的一个实例由软约束和硬约束组成，目标是在满足所有硬约束的同时最大化满足的软约束的权重。这两个扩展包含了许多CSP没有捕捉到的基本问题，并在更一般的框架中挑战了关于CSP的传统理论。MAX-2-SAT和MAX-Horn-SAT是仅有的两类非平凡布尔CSP，它们具有稳健的满足性算法，即在给定一个(1−)-可满足实例的情况下，找到一个至少满足(1-ε)部分约束的赋值，其中g(−ε0为ε)→0，且g(0)=0)。我们证明了这些问题在平衡约束或硬约束下的不可逼近性，表明每个变量都显著地改变了问题的性质(以不同的方式)。例如，判断2-SAT的一个实例是否允许平衡分配是NP-Hard的，并且对于具有硬约束的MAX-2-SAT，即使在(1−ε)可满足的实例上也很难找到恒因子近似(特别是，具有硬约束的版本不允许稳健的可满足性算法)。我们还研究了在更大的区域上捕获有序约束的某一CSP的硬度结果：我们证明了硬约束排除了常数因子近似算法。我们所有的硬性结果几乎都是最优的--它们完全排除了具有某些性质的算法，或者可以通过对现有算法的简单扩展来匹配。
We study two natural extensions of Constraint Satisfaction Problems (CSPs). Balance-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of Hard-Max-CSP consists of soft constraints and hard constraints, and the goal is to maximize the weight of satisfied soft constraints while satisfying all the hard constraints. These two extensions contain many fundamental problems not captured by CSPs, and challenge traditional theories about CSPs in a more general framework. Max-2-SAT and Max-Horn-SAT are the only two nontrivial classes of Boolean CSPs that admit a robust satisfibiality algorithm, i.e., an algorithm that finds an assignment satisfying at least (1 − g(ε)) fraction of constraints given a (1 − ε)-satisfiable instance, where g(ε) → 0 as ε → 0, and g(0) = 0. We prove the inapproximability of these problems with balance or hard constraints, showing that each variant changes the nature of the problems significantly (in different ways). For instance, deciding whether an instance of 2-SAT admits a balanced assignment is NP-hard, and for Max-2-SAT with hard constraints, it is hard to find a constant-factor approximation even on (1 − ε)-satisfiable instances (in particular, the version with hard constraints does not admit a robust satisfiability algorithm). We also study hardness results for a certain CSP over a larger domain capturing ordering constraints: we show that hard constraints rule out constant-factor approximation algorithms. All our hardness results are almost optimal — they completely rule out algorithms with certain properties, or can be matched by simple extensions to existing algorithms.