Towards a characterization of constant-factor approximable finite-valued CSPs
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Dalmau, Víctor
- dc.contributor.author Krokhin, Andrei
- dc.contributor.author Manokaran, Rajsekar
- dc.date.accessioned 2021-06-04T07:13:26Z
- dc.date.available 2021-06-04T07:13:26Z
- dc.date.issued 2018
- dc.description.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 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 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.
- dc.format.mimetype application/pdf
- dc.identifier.citation Dalmau V, Krokhin A, Manokaran R. Towards a characterization of constant-factor approximable finite-valued CSPs. J Comput Syst Sci. 2018;97:14-27. DOI: 10.1016/j.jcss.2018.03.003
- dc.identifier.doi http://dx.doi.org/10.1016/j.jcss.2018.03.003
- dc.identifier.issn 0022-0000
- dc.identifier.uri http://hdl.handle.net/10230/47765
- dc.language.iso eng
- dc.publisher Elsevier
- dc.relation.ispartof Journal of Computer and System Sciences. 2018;97:14-27
- dc.rights © Elsevier http://dx.doi.org/10.1016/j.jcss.2018.03.003
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Constraint satisfaction problem
- dc.subject.keyword Approximation algorithms
- dc.subject.keyword Universal algebra
- dc.title Towards a characterization of constant-factor approximable finite-valued CSPs
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion