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
Based on joint papers with Igor Gridchyn, Andrei Krokhin, Michal Rolinek, Johan
Thapper and Stanislav Zivny.