---
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@'
...