---
_id: '2271'
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.
    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. "
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Johan
  full_name: Thapper, Johan
  last_name: Thapper
- first_name: Stanislav
  full_name: Živný, Stanislav
  last_name: Živný
citation:
  ama: Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued
    CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href="https://doi.org/10.1137/130945648">10.1137/130945648</a>
  apa: Kolmogorov, V., Thapper, J., &#38; Živný, S. (2015). The power of linear programming
    for general-valued CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/130945648">https://doi.org/10.1137/130945648</a>
  chicago: Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of
    Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>.
    SIAM, 2015. <a href="https://doi.org/10.1137/130945648">https://doi.org/10.1137/130945648</a>.
  ieee: V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming
    for general-valued CSPs,” <i>SIAM Journal on Computing</i>, vol. 44, no. 1. SIAM,
    pp. 1–36, 2015.
  ista: Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for
    general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36.
  mla: Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued
    CSPs.” <i>SIAM Journal on Computing</i>, vol. 44, no. 1, SIAM, 2015, pp. 1–36,
    doi:<a href="https://doi.org/10.1137/130945648">10.1137/130945648</a>.
  short: V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015)
    1–36.
date_created: 2018-12-11T11:56:41Z
date_published: 2015-02-01T00:00:00Z
date_updated: 2025-09-23T14:14:57Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/130945648
external_id:
  arxiv:
  - '1311.4219'
  isi:
  - '000353967100001'
intvolume: '        44'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1311.4219
month: '02'
oa: 1
oa_version: Preprint
page: 1 - 36
publication: SIAM Journal on Computing
publication_status: published
publisher: SIAM
publist_id: '4673'
quality_controlled: '1'
related_material:
  record:
  - id: '2518'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: The power of linear programming for general-valued CSPs
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 44
year: '2015'
...