Skip to main content

Research Repository

Advanced Search

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

Dalmau, V.; Krokhin, A.; Manokaran, R.

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


Authors

V. Dalmau

R. Manokaran



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.

Citation

Dalmau, V., Krokhin, A., & Manokaran, R. (2018). Towards a characterization of constant-factor approximable Finite-Valued CSPs. Journal of Computer and System Sciences, 97, 14-27. https://doi.org/10.1016/j.jcss.2018.03.003

Journal Article Type Article
Acceptance Date Mar 16, 2018
Online Publication Date Apr 17, 2018
Publication Date Nov 1, 2018
Deposit Date Apr 16, 2018
Publicly Available Date Apr 17, 2019
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 97
Pages 14-27
DOI https://doi.org/10.1016/j.jcss.2018.03.003
Related Public URLs https://arxiv.org/abs/1610.01019

Files





You might also like



Downloadable Citations