Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
复制标题
最大化乘积格上的超模函数，并应用于最大约束满足
DOI：
10.1137/060669565
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
B. Larose
中科院分区：
文献类型：
--
作者：
A. Krokhin;B. Larose
最近，一个强有力的链接已被发现之间的超模块化的最优化问题，称为最大约束满足问题。本文件加强了这一联系。研究了由预言机给出的定义在固定有限格的n个拷贝的乘积上的超模函数的最大化问题。我们展示了一个大类的有限格，这个问题可以解决在预言多项式时间在$n$。我们还获得了新的大类易处理的最大约束满足问题。
Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a supermodular function which is defined on a product of $n$ copies of a fixed finite lattice and given by an oracle. We exhibit a large class of finite lattices for which this problem can be solved in oracle-polynomial time in $n$. We also obtain new large classes of tractable maximum constraint satisfaction problems.