The complexity of conservative valued CSPs
The complexity of conservative valued CSPs
复制标题
保守价值 CSP 的复杂性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Stanislav Živný
中科院分区：
文献类型：
--
作者：
V. Kolmogorov;Stanislav Živný
我们研究的复杂性值约束满足问题（VCSPs）参数化的约束语言，一组固定的成本函数在有限的区域。问题的一个实例由语言中的成本函数之和指定，目标是最小化该和。在唯一博弈猜想下，有限值VCSP的可逼近性得到了很好的理解，参见Raghavendra [2008]。然而，没有有限值VCSP的特征，更不用说一般值VCSP，可以在多项式时间内精确求解，从而从组合优化的角度提供见解。
我们考虑的情况下，语言包含所有可能的一元成本函数。在仅由{0，∞}值成本函数组成的语言的情况下（即，关系），这些语言被称为保守的，并由Bulatov [2003，2011]和最近由Barto [2011]研究。由于我们研究值语言，我们称一个语言是保守的，如果它包含所有有限值的一元代价函数。Cohen等人[2006]研究了布尔域上的保守值语言的计算复杂性，Deineko等人[2008]研究了{0，1}值语言（又称Max-CSP），Takhanov [2010 a]研究了包含所有有限值一元代价函数的{0，∞}值语言（又称Max-CSP）。Min-Cost-Hom）。
我们证明了保守值语言的Schaefer式二分法定理：如果语言中的所有代价函数都满足一定的条件（由STP和MJN多态化的互补组合指定），则任何实例都可以在多项式时间内求解（通过本文开发的新算法），否则语言是NP难的。这是第一个完整的复杂性分类的一般值约束语言在非布尔域。非布尔域问题的复杂性分类比布尔域问题的复杂性分类困难得多，这是一个普遍现象。我们为易处理的情况提出的多项式时间算法是子模最小化问题的推广，也是Cohen等人[2008]的结果。
我们的结果推广了Takhanov [2010 a]和Cohen et al. [2006]和Deineko et al. [2008]的结果（结果的子集）。此外，我们的结果不像Deineko等人[2008]那样依赖于任何计算机辅助搜索，并为证明有限值和一般值语言的硬度提供了一个强大的工具。
We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimize the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well understood, see Raghavendra [2008]. However, there is no characterization of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimization perspective.
We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0,∞}-valued cost functions (i.e., relations), such languages have been called conservative and studied by Bulatov [2003, 2011] and recently by Barto [2011]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [2006] for languages over Boolean domains, by Deineko et al. [2008] for {0,1}-valued languages (a.k.a Max-CSP), and by Takhanov [2010a] for {0,∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom).
We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimorphisms), then any instance can be solved in polynomial time (via a new algorithm developed in this article), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains are significantly harder than the Boolean cases. The polynomial-time algorithm we present for the tractable cases is a generalization of the submodular minimization problem and a result of Cohen et al. [2008].
Our results generalize previous results by Takhanov [2010a] and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [2008], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.
DOI：
10.1016/j.artint.2011.02.003
发表时间：
2010-08
期刊：
Artif. Intell.
影响因子：
--
作者：
Martin C. Cooper;Stanislav Živný
通讯作者：
Martin C. Cooper;Stanislav Živný
DOI：
10.1016/j.jcss.2014.06.006
发表时间：
2012-08
期刊：
--
影响因子：
--
作者：
X. Chen;M. Dyer;L. A. Goldberg;M. Jerrum;P. Lu;Colin McQuillan;David Richerby
通讯作者：
X. Chen;M. Dyer;L. A. Goldberg;M. Jerrum;P. Lu;Colin McQuillan;David Richerby