权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Submodular optimization, lattice theory and maximum constraint satisfaction problems

子模优化、格理论和最大约束满足问题

基本信息

批准号：
EP/H000666/1
负责人：
Andrei Krokhin
金额：
$ 37.88万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FH000666%2F1
关键词：
Submodular optimization lattice theory maximum

项目摘要

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.

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