Robust satisfiability of constraint satisfaction problems
Robust satisfiability of constraint satisfaction problems
复制标题
约束满足问题的鲁棒可满足性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Kozik
中科院分区：
文献类型：
--
作者：
L. Barto;M. Kozik
一个约束满足问题的算法被称为鲁棒的，如果它输出的分配满足至少（1-g（ε））-分数的约束给定的（1-ε）-可满足的情况下，其中g（ε）-> 0作为ε -> 0，$g（0）=0。Guruswami和Zhou推测了约束语言的一个特征，其中相应的约束满足问题需要一个高效的鲁棒算法。这篇论文证实了他们的猜想。
An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least (1-g(ε))-fraction of the constraints given a (1-ε)-satisfiable instance, where g(ε) -> 0 as ε -> 0, $g(0)=0. Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction problem admits an efficient robust algorithm. This paper confirms their conjecture.