Submodular optimization, lattice theory and maximum constraint satisfaction problems

次模函数和超模函数是定义在集合的幂集中的特殊函数。这类函数是组合优化中的一个关键概念，它们在其他地方有许多应用。最小化给定的子模函数的问题SFM是最重要的易于处理的优化问题之一。我们的第一个目标是研究推广到任意有限格的SFM的算法方面，而不仅仅是子集族(从而表示与包含的顺序不同的顺序)。在我们的设置中，经典的SFM将对应于二元格子的最简单的非平凡情况。最近，人们发现格上的子模和超模的性质与所谓的最大约束满足问题(Max CSP)的可处理性之间存在着很强的联系，这是计算机科学和人工智能领域中非常活跃的研究问题。在Max CSP中，一个人被赋予一个关于重叠变量集的约束集合(可能是加权的)，目标是找到从固定的域到具有最大数量(或总权重)满足约束的变量的赋值。我们打算全面调查这种联系。我们还将考虑将Max CSP框架扩展到处理可取性而不仅仅是可行性的有价值的或软的约束，从而定义一个更一般的优化问题。因此，我们的第二个目标是理解在一大类(通常是困难的)组合优化问题中可处理性的原因。

Sub- and supermodular functions are special functions defined on the powerset of a set. Such functions are a key concept in combinatorial optimization, and they have numerous applications elsewhere. The problem, SFM, of minimizing a given submodular function is one of the most important tractable optimization problems. Our first goal is to investigate algorithmic aspects of the SFM generalized to arbitrary finite lattices rather than just families of subsets (thus representing order different from that of inclusion). In our setting, the classical SFM would correspond to the simplest non-trivial case of the two-element lattice. We intend to find a new wide natural class of tractable optimization problems.Recently, a strong connection was discovered between the properties of sub- and supermodularity on lattices and tractability of the so-called maximum constraint satisfaction problems (Max CSP), which are very actively studied problems in computer science and artificial intelligence. In a Max CSP, one is given a collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to find an assignment of values from a fixed domain to the variables with a maximum number (or total weight) of satisfied constraints. We intend to investigate the full extent of this connection. We will also consider an extension of the Max CSP framework to valued, or soft, constraints that deal with desirability rather than just feasibility, and hence define a more general optimization problem. Thus, our second goal is to understand the reasons for tractability within a wide class of (generally hard) combinatorial optimization problems.