Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Towards a characterization of constant-factor approximable Finite-Valued CSPs.

Dalmau, V. and Krokhin, A. and Manokaran, R. (2018) 'Towards a characterization of constant-factor approximable Finite-Valued CSPs.', Journal of computer and system sciences., 97 . pp. 14-27.

Abstract

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under a mild technical condition, the basic LP relaxation is optimal for constant-factor approximation for VCSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we give new natural algebraic conditions for the finiteness of the integrality gap for the basic LP relaxation of VCSP(Γ) and show how this leads to efficient constant-factor approximation algorithms for several examples that cover all previously known cases that are NP-hard to solve to optimality but admit constant-factor approximation. Finally, we show that the absence of another algebraic condition leads to NP-hardness of constant-factor approximation. Thus, our results indicate where the boundary of constant-factor approximability for VCSPs lies.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(355Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.jcss.2018.03.003
Publisher statement:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:16 March 2018
Date deposited:18 April 2018
Date of first online publication:17 April 2018
Date first made open access:17 April 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar