---
_id: '2518'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive
    characterization. In: Vol 7965. Springer; 2013:625-636. doi:<a href="https://doi.org/10.1007/978-3-642-39206-1_53">10.1007/978-3-642-39206-1_53</a>'
  apa: 'Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs:
    A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP:
    Automata, Languages and Programming, Riga, Latvia: Springer. <a href="https://doi.org/10.1007/978-3-642-39206-1_53">https://doi.org/10.1007/978-3-642-39206-1_53</a>'
  chicago: 'Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued
    CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. <a href="https://doi.org/10.1007/978-3-642-39206-1_53">https://doi.org/10.1007/978-3-642-39206-1_53</a>.'
  ieee: 'V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A
    constructive characterization,” presented at the ICALP: Automata, Languages and
    Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.'
  ista: 'Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs:
    A constructive characterization. ICALP: Automata, Languages and Programming, LNCS,
    vol. 7965, 625–636.'
  mla: 'Kolmogorov, Vladimir. <i>The Power of Linear Programming for Finite-Valued
    CSPs: A Constructive Characterization</i>. Vol. 7965, no. 1, Springer, 2013, pp.
    625–36, doi:<a href="https://doi.org/10.1007/978-3-642-39206-1_53">10.1007/978-3-642-39206-1_53</a>.'
  short: V. Kolmogorov, in:, Springer, 2013, pp. 625–636.
conference:
  end_date: 2013-07-12
  location: Riga, Latvia
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2013-07-08
corr_author: '1'
date_created: 2018-12-11T11:58:08Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2025-09-23T14:14:56Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-39206-1_53
external_id:
  arxiv:
  - '1207.7213'
intvolume: '      7965'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1207.7213
month: '07'
oa: 1
oa_version: Preprint
page: 625 - 636
publication_status: published
publisher: Springer
publist_id: '4383'
quality_controlled: '1'
related_material:
  record:
  - id: '2271'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: 'The power of linear programming for finite-valued CSPs: A constructive characterization'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7965
year: '2013'
...