An Algebraic Theory of Complexity for Discrete Optimization
An Algebraic Theory of Complexity for Discrete Optimization
复制标题
离散优化的复杂性代数理论
DOI：
10.1137/130906398
复制
发表时间：
2013
影响因子：
1.6
通讯作者：
Cohen D
中科院分区：
文献类型：
--
作者：
Cohen D
离散优化问题出现在许多不同的领域，并以许多不同的名称进行研究。在许多这样的问题中，要优化的量可以表示为限制形式的函数之和。在这里，我们提出了一个统一的复杂性理论，这类问题。我们证明了有限域离散优化问题的复杂性是由目标函数的某些代数性质决定的，我们称之为加权多态性。我们定义了一个伽罗瓦连接集之间的有理值函数和加权多态性集，并显示如何封闭集的伽罗瓦连接的特点。这些结果为研究离散优化问题的复杂性提供了一种新的途径。我们使用这种方法来确定某些最大的一般问题的易处理的子问题，从而得出一个完整的分类的布尔情况下的复杂性。
Discrete optimization problems arise in many different areas and are studied under many different names. In many such problems the quantity to be optimized can be expressed as a sum of functions of a restricted form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a finite-domain discrete optimization problem is determined by certain algebraic properties of the objective function, which we callweighted polymorphisms. We define a Galois connection between sets of rational-valued functions and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterized. These results provide a new approach to studying the complexity of discrete optimization. We use this approach to identify certain maximal tractable subproblems of the general problem and hence derive a complete classification of complexity for the Boolean case.
登录
查看更多内容
DOI：
10.1016/j.artint.2011.02.003
发表时间：
2010-08
期刊：
Artif. Intell.
影响因子：
--
作者：
Martin C. Cooper;Stanislav Živný
通讯作者：
Martin C. Cooper;Stanislav Živný
DOI：
--
发表时间：
1995
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
N. Creignou
通讯作者：
N. Creignou
DOI：
--
发表时间：
2001
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
A. Bulatov;A. Krokhin;P. Jeavons
通讯作者：
P. Jeavons
代数方程类中同余关系的分布性和置换性
DOI：
--
发表时间：
1963
期刊：
影响因子：
--
作者：
A. Pixley
通讯作者：
A. Pixley
影响因子：
32.8
作者：
Wainwright, Martin J.;Jordan, Michael I.
通讯作者：
Jordan, Michael I.