The power of linear programming for valued CSPs: a constructive characterization

Vladimir Kolmogorov

A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the pr…