--- res: bibo_abstract: - 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 problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Vladimir foaf_name: Kolmogorov, Vladimir foaf_surname: Kolmogorov foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87 bibo_doi: 10.1007/978-3-642-39206-1_53 bibo_issue: '1' bibo_volume: 7965 dct_date: 2013^xs_gYear dct_language: eng dct_publisher: Springer@ dct_title: 'The power of linear programming for finite-valued CSPs: A constructive characterization@' ...