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.