Beating a Random Assignment : Approximating Constraint Satisfaction Problems
Beating a Random Assignment : Approximating Constraint Satisfaction Problems
复制标题
击败随机分配：近似约束满足问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Gustav Hast
中科院分区：
文献类型：
--
作者：
Gustav Hast
CSP的一个布尔约束满意度问题由一组在一组布尔变量上作用的约束是为了找到满足所有约束的变量的分配。约束有一个重量，目的是找到一个分配，以使满足约束的权重指定允许哪些类型的约束我们创建的子问题，例如最大kcsp的实例。在大多数k上，另一个问题是最大CSP（P），其中P是一个预测，即在此实例p中确定是否满足约束。最大CSP（p）是针对K≥2的NP固定，而prepticates P取决于至少两个输入值。值得一提的是，HASTAD表明使用这种随机分配方法对于近似CSP（P）来说是最佳的。他们使用此方法表明，对于Arity二的prepticate P，可以通过将ARITY三的所有谓词表征为抗近似值，以超过最大CSP（P）的随机分配我们考虑了大于三个的谓词我们表明，较少的非认可输入的谓词是抗抗性的，并且很少的接受输入的谓词不是抗近似值，我们研究了ARITY的谓词。通过随机分配和以前没有算法，在本文中，概率ω（2k+log k-log log k） - 最大kcsp的概率ω（2k+log k-log log k）中，算法超过了较小的恒定因子。
An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not. Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Hastad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not. In this thesis we consider predicates of arity larger than three. We extend the work of Hastad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types. Max kCSP is 2-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic Ω (2k+log k-log log k)-approximation for Max kCSP is presented.