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.
展开▼
机译：最近，在晶格上的超模量和称为最大约束满足问题的最优化问题的易处理性之间发现了牢固的联系。本文加强了这一联系。我们研究最大化超模函数的问题，该函数是在固定有限格的$ n $个副本的乘积上定义的，并且由oracle给出。我们展示了一大类有限晶格，可以在$ n $的oracle多项式时间内解决此问题。我们还获得了新的大类可处理的最大约束满足问题。
展开▼
