Mathematical Foundations of Computer Science 2011
Mathematical Foundations of Computer Science 2011
复制标题
计算机科学数学基础 2011
DOI：
10.1007/978-3-642-22993-0_23
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Cohen D
中科院分区：
文献类型：
--
作者：
Cohen D
任何优化问题的复杂性都取决于目标函数的形式。有值约束满足问题是离散优化问题，其中要最小化的函数被给定为在指定变量子集上定义的成本函数的总和。这些成本函数是从一些固定的可用成本函数集合中选择的，称为值约束语言。在本文中，我们表明，当成本是非负有理数或无穷大，然后值约束问题的复杂性是由一定的代数性质的值约束语言，我们称之为加权多态性。我们定义了一个伽罗瓦连接值约束语言和加权多态性集之间，并显示如何封闭的伽罗瓦连接的特点。这些结果为寻找易处理的值约束语言提供了一种新的途径。
The complexity of any optimisation problem depends critically on the form of the objective function. Valued constraint satisfaction problems are discrete optimisation problems where the function to be minimised is given as a sum of cost functions defined on specified subsets of variables. These cost functions are chosen from some fixed set of available cost functions, known as a valued constraint language. We show in this paper that when the costs are non-negative rational numbers or infinite, then the complexity of a valued constraint problem is determined by certain algebraic properties of this valued constraint language, which we callweighted polymorphisms. We define a Galois connection between valued constraint languages and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised. These results provide a new approach in the search for tractable valued constraint languages.