The Complexity of General-Valued CSPs
The Complexity of General-Valued CSPs
复制标题
通用价值 CSP 的复杂性
DOI：
10.1109/focs.2015.80
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Kolmogorov V
中科院分区：
文献类型：
--
作者：
Kolmogorov V
赋值约束满足问题(VCSP)的一个实例由一个有限变量集、一个有限标记域和一个函数和给出，每个函数依赖于变量的一个子集。每个函数可以采用有限的值来指定为其变量赋值标签的成本，也可以取无穷大的值来表示不可行的赋值。目标是找到使和最小的变量的标签赋值。我们研究，假设PnP，这个非常一般的问题的复杂性如何取决于实例中允许的函数集，即所谓的约束语言。当所有允许的函数都取值时，对应于普通的CSP，其中只处理可行性问题，没有优化。这种情况是代数CSP二分猜想的主题，它预测了对于哪些约束语言CSP是可处理的(即，在多项式时间内可解)，以及对于哪些约束语言它们是NP难的。当所有允许的函数只取有限值时，对应于有限值CSP，其中可行性方面是微不足道的，并且只处理优化问题。Thpper和Živný对有限值CSP的复杂性进行了完全分类。Kozik和Ochremiak最近给出了具有固定约束语言的通值CSP可解性的一个代数必要条件。作为我们的主要结果，我们证明了如果一种约束语言满足这个代数必要条件，并且与该语言对应的VCSP的可行性CSP(即判断给定实例是否有可行解的问题)是可处理的，则该VCSP是可处理的。该算法是可行性CSP假设算法和标准LP松弛算法的简单组合。作为推论，我们得到了对普通CSP的二分性意味着对一般值CSP的二分性。
An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that PNP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values incorresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.
登录
查看更多内容
Sherali-Adams 放宽对于普通价值 CSP 的作用
DOI：
--
发表时间：
2016
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Johan Thapper;Stanislav Živný
通讯作者：
Stanislav Živný
影响因子：
1.6
作者：
Cohen D
通讯作者：
Cohen D
有限值 CSP 线性规划的威力：建设性表征
DOI：
10.1007/978-3-642-39206-1_53
发表时间：
2013
期刊：
2013 IEEE 25th International Conference on Tools with Artificial Intelligence
影响因子：
--
作者：
V. Kolmogorov
通讯作者：
V. Kolmogorov
影响因子：
32.8
作者：
Wainwright, Martin J.;Jordan, Michael I.
通讯作者：
Jordan, Michael I.
超模函数和 MAX CSP 的复杂性
DOI：
10.1016/j.dam.2005.03.003
发表时间：
2005
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
D. Cohen;Martin C. Cooper;P. Jeavons;A. Krokhin
通讯作者：
A. Krokhin