The complexity of finite-valued CSPsReportar como inadecuado




The complexity of finite-valued CSPs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Thapper, J and Zivny, S, The complexity of finite-valued CSPs. Journal of the ACM, 63 (4).Citable link to this page:

 

The complexity of finite-valued CSPs

Abstract: We study the computational complexity of exact minimisation of separable rational-valued discretefunctions. Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valuedconstraint language. The valued constraint satisfaction problem, VCSP (Γ), is the problem of minimisinga function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exactsolvability for all finite-valued constraint languages defined on domains of arbitrary finite size.We show that every constraint language Γ either admits a binary symmetric fractional polymorphism inwhich case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies asimple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ).

Peer Review status:Peer reviewedPublication status:PublishedVersion:Accepted manuscriptNotes:Copyright 2016 ACM. This is the author accepted manuscript version of the article. The final version may be available online from the Association for Computing Machinery at https://doi.org/10.1145/2974019.

Bibliographic Details

Publisher: Association for Computing Machinery

Publisher Website: http://www.acm.org/

Journal: Journal of the ACMsee more from them

Publication Website: http://jacm.acm.org/

Volume: 63

Extent: Article No. 37Identifiers

Urn: uuid:9030708d-1cf0-435f-80ad-d591addd1668

Doi: https://doi.org/10.1145/2974019

Source identifier: 574782

Issn: 1535-9921 Item Description

Type: Journal article;

Version: Accepted manuscript Tiny URL: pubs:574782

Relationships





Autor: Thapper, J - grantNumberFP7-2007-2013 Grant Agreement no. 257039 fundingEuropean Research Council - - - Zivny, S - institutionUni

Fuente: https://ora.ox.ac.uk/objects/uuid:9030708d-1cf0-435f-80ad-d591addd1668



DESCARGAR PDF




Documentos relacionados