Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
复制标题
具有多项式损失的稳健算法，可实现近乎一致的 CSP
DOI：
10.1137/18m1163932
复制
发表时间：
2019
影响因子：
1.6
通讯作者：
Dalmau V
中科院分区：
文献类型：
--
作者：
Dalmau V
约束满足问题（CSP）的一个例子是由一个家庭的约束重叠的变量集，目标是从一个固定的域的变量，使所有的约束都得到满足的值。在优化版本中，目标是最大化满足的约束的数量。如果CSP的近似算法输出满足任何可满足实例上的一小部分约束的分配，则该算法被称为鲁棒的，其中损失函数为。我们研究了CSP的鲁棒逼近性如何依赖于实例中允许的约束关系集，即所谓的约束语言。 Barto和Kozik已经描述了所有允许鲁棒的多项式时间算法的约束语言，具体来说，损失的一般界是双指数的。人们自然会问，什么时候可以实现更好的损失，特别是多项式损失。在本文中，我们认为CSP的约束语言具有近多态性。这个一般条件几乎与具有多项式损失的鲁棒算法的已知必要条件相匹配。我们给出了两个随机的强大的算法与多项式损失这样的CSP：一个工程的任何接近多态性和参数的损失取决于域的大小和arity的关系，而另一个工程的一个特殊的三元接近多态性操作称为对偶的接近多态性与任何域的大小。 在后一种情况下，CSP是一个共同的推广唯一的游戏与一个固定的域和2-Sat。 在前一种情况下，我们使用代数方法的CSP。 这两种情况下使用标准的半定规划松弛的CSP。
An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints. An approximation algorithm for a CSP is called robust if it outputs an assignment satisfying an-fraction of constraints on any-satisfiable instance, where the loss functionis such thatas. We study how the robust approximability of CSPs depends on the set of constraint relations allowed in instances, the so-called constraint language. All constraint languages admitting a robust polynomial-time algorithm (with some) have been characterized by Barto and Kozik, with the general bound on the lossbeing doubly exponential, specifically. It is natural to ask when a better loss can be achieved, in particular polynomial lossfor some constant. In this paper, we consider CSPs with a constraint language having a near-unanimity polymorphism. This general condition almost matches a known necessary condition for having a robust algorithm with polynomial loss. We give two randomized robust algorithms with polynomial loss for such CSPs: one works for any near-unanimity polymorphism and the parameterin the loss depends on the size of the domain and the arity of the relations in, while the other works for a special ternary near-unanimity operation called the dual discriminator withfor any domain size. In the latter case, the CSP is a common generalization ofUnique Gameswith a fixed domain and2-Sat. In the former case, we use the algebraic approach to the CSP. Both cases use the standard semidefinite programming relaxation for the CSP.