skip to content

Valued Constraint Satisfaction Problems

Presented by: 
Vladimir Kolmogorov
Wednesday 6th September 2017 - 11:10 to 12:00
INI Seminar Room 1
I will consider the Valued Constraint Satisfaction Problem (VCSP), whose goal is to minimize a sum of local terms where each term comes from a fixed set of functions (called a "language") over a fixed discrete domain. I will present recent results characterizing languages that can be solved using the basic LP relaxation. This includes languages consisting of submodular functions, as well as their generalizations.

One of such generalizations is k-submodular functions. In the second part of the talk I will present an application of such functions in computer vision.

Based on joint papers with Igor Gridchyn, Andrei Krokhin, Michal Rolinek, Johan Thapper and Stanislav Zivny. 
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons