Submodular optimization, lattice theory and maximum constraint satisfaction problems

点击翻译按钮获取中文摘要

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.