Access Restriction

Author Thapper, Johan ♦ Ivn, Stanislav
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Discrete optimization ♦ Complexity ♦ Dichotomy ♦ Valued constraint satisfaction problems
Abstract We study the computational complexity of exact minimization of rational-valued discrete functions. Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimizing a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for $\textit{all}$ finite-valued constraint languages defined on domains of $\textit{arbitrary}$ finite size. We show that every constraint language Γ either admits a binary symmetric fractional polymorphism, in which case the basic linear programming relaxation solves any instance of VCSP(Γ) exactly, or Γ satisfies a simple hardness condition that allows for a polynomial-time reduction from Max-Cut to VCSP(Γ).
Description Author Affiliation: University of Oxford, Oxford, United Kingdom (ivn, Stanislav); Université Paris-Est Marne-la-Vallée, France (Thapper, Johan)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 33
Starting Page 1
Ending Page 33

Open content in new tab

   Open content in new tab
Source: ACM Digital Library