---
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.
    Finite-valued constraint languages contain functions that take on rational costs
    and general-valued constraint languages contain functions that take on rational
    or infinite costs. An instance of the problem is specified by a sum of functions
    from the language with the goal to minimise the sum. This framework includes and
    generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint
    satisfaction problems (Max-CSPs).\r\nOur main result is a precise algebraic characterisation
    of valued constraint languages whose instances can be solved exactly by the basic
    linear programming relaxation (BLP). For a general-valued constraint language
    Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional
    polymorphism of every arity. For a finite-valued constraint language Γ, BLP is
    a decision procedure if and only if Γ admits a symmetric fractional polymorphism
    of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism
    of arity 2.\r\nUsing these results, we obtain tractability of several novel and
    previously widely-open classes of VCSPs, including problems over valued constraint
    languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also
    known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly)
    tree-submodular on arbitrary trees. @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
  - foaf_Person:
      foaf_givenName: Johan
      foaf_name: Thapper, Johan
      foaf_surname: Thapper
  - foaf_Person:
      foaf_givenName: Stanislav
      foaf_name: Živný, Stanislav
      foaf_surname: Živný
  bibo_doi: 10.1137/130945648
  bibo_issue: '1'
  bibo_volume: 44
  dct_date: 2015^xs_gYear
  dct_identifier:
  - UT:000353967100001
  dct_language: eng
  dct_publisher: SIAM@
  dct_title: The power of linear programming for general-valued CSPs@
...