This is joint work with Stanislav Zivny.

In a valued constraint satisfaction problem (VCSP), a *language* is a fixed set of cost functions over a fixed domain. An *instance* from this language is specified by a sum of cost functions from the language, and the goal is to minimise the sum. Classifying the complexity of such minimisation problems for different languages has been an active research area. While a significant progress has been made for CSPs (i.e. languages containing only {0,∞}-valued functions, or relations), fewer results are known for the more general case of VCSPs. I will talk about our recent work on general valued languages containing all possible unary cost functions. We call such languages *conservative*. (This definition differs from the one used in the CSP literature for relations, where a language was called conservative if it contains all possible unary relations.) We prove a Schaefer-style dichotomy theorem for conservative languages: if all functions in the language satisfy a certain condition then the language can be minimized in polynomial time (via a new algorithm that we developed), otherwise it is NP-hard. This is the first complete classification for general-valued constraint languages over nonBoolean domains. Our work generalises previous results obtained by Cohen et al. [AIJ’06], Takhanov [STACS’10], and Deineko et al. [JACM’08]. Moreover, our proofs do not rely on any computer-assisted search as in Deineko et al. [JACM’08].