Robust Satisfiability for CSPs Hardness and Algorithmic Results
Robust Satisfiability for CSPs Hardness and Algorithmic Results
复制标题
CSP 硬度和算法结果的稳健可满足性
DOI：
10.1145/2540090
复制
发表时间：
2013
影响因子：
0.7
通讯作者：
Dalmau V
中科院分区：
文献类型：
--
作者：
Dalmau V
一个约束满足问题的算法被称为鲁棒的，如果它输出的分配满足每个（1-ε）-可满足实例的至少一个（1-f（ε））-约束分数（即，使得至多需要移除ε分数的约束以使实例可满足），其中f（ε）→ 0 asε→ 0。我们建立了一个分析约束满足问题的代数框架，允许一个有效的鲁棒算法与函数f的给定的增长率。我们使用这个框架来获得硬度结果。我们还描述了三类问题，允许一个有效的鲁棒算法，使fisO（1/log（1/ε）），O（ε1/k），其中some k> 1，和O（ε）。最后，我们给出了鲁棒可满足性的一个完整分类，并给出了布尔情形下的一个f。
An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 −f(ε))-fraction of constraints for each (1 −ε)-satisfiable instance (i.e., such that at most aε-fraction of constraints needs to be removed to make the instance satisfiable), wheref(ε) → 0 asε→ 0. We establish an algebraic framework for analyzing constraint satisfaction problems admitting an efficient robust algorithm with functionsfof a given growth rate. We use this framework to derive hardness results. We also describe three classes of problems admitting an efficient robust algorithm such thatfisO(1/log (1/ε)),O(ε1/k) for somek> 1, andO(ε), respectively. Finally, we give a complete classification of robust satisfiability with a givenffor the Boolean case.