Discrete Mathematics and Optimization Seminar

---

ANDREI KROKHIN
Durham University
Monday November 13th at 4.30pm
Burnside 1205



Title. Maximum constraint satisfaction and supermodular optimisation on lattices.

Abstract. The maximum constraint satisfaction problem (Max CSP) provides a unified framework which can express many combinatorial
optimisation problems including Max Cut and Max k-Sat. An instance of Max CSP consists of a collection of weighted constraints on
overlapping sets of variables, and the goal is to find values for the variables that maximise the total weight of simultaneously
satisfied constraints. We will consider the problem of determining how exactly the complexity of Max CSPs depends on the type of
constraints allowed in instances. We will discuss the recently discovered strong link between tractability of Max CSPs and
supermodular functions defined on products of lattices, and present some classification results based on this link.