Supermodular functions and the complexity of MAX CSP
Supermodular functions and the complexity of MAX CSP
复制标题
超模函数和 MAX CSP 的复杂性
DOI：
10.1016/j.dam.2005.03.003
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Krokhin
中科院分区：
文献类型：
--
作者：
D. Cohen;Martin C. Cooper;P. Jeavons;A. Krokhin
本文研究了任意有限域上的最大约束满足问题（MAX CSP）的复杂性。MAX CSP的一个实例由一组变量和一组约束组成，这些约束应用于这些变量的某些指定子集;目标是找到最大化同时满足的约束数量的变量值。利用有限格序集上的次模函数和超模函数的理论，我们得到了任意有限域上MAX CSP有效可解情形的第一个例子。此外，我们提供了第一个二分法的结果，一类特殊的非布尔MAX CSP，通过考虑二元约束的超模函数的全序集。最后，我们证明了在非布尔域的等式约束是非超模的，并且，当与一些简单的一元约束相结合时，会产生MAX CSP的情况，甚至很难近似。
In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. Using the theory of sub- and supermodular functions on finite lattice-ordered sets, we obtain the first examples of general families of efficiently solvable cases of MAX CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean MAX CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of MAX CSP which are hard even to approximate.