Welcome to the UPF Digital Repository

Towards a characterization of constant-factor approximable Min CSPs

Show simple item record

dc.contributor.author Dalmau, Víctor
dc.contributor.author Krokhin, Andrei
dc.contributor.author Manokaran, Rajsekar
dc.date.accessioned 2018-02-05T08:36:17Z
dc.date.available 2018-02-05T08:36:17Z
dc.date.issued 2015
dc.identifier.citation Dalmau V, Krokhin A, Manokaran R. Towards a characterization of constant-factor approximable Min CSPs. In: Twenty-sixth annual ACM-SIAM symposium on Discrete algorithms; 2015 Jan 4-6; San Diego, CA. Philadelphia (PA): SIAM; 2015. p. 847-57. DOI: 10.1137/1.9781611973730.58
dc.identifier.uri http://hdl.handle.net/10230/33800
dc.description Comunicació presentada al Twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, celebrat els dies 4 a 6 de gener de 2015 a San Diego, Califòrnia.
dc.description.abstract We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given instance of CSP(Γ). A recent result of Ene et al. says that, under the mild technical condition that Γ contains the equality relation, the basic LP relaxation is optimal for constant-factor approximation for Min CSP(Γ) unless the Unique Games Conjecture fails. Using the algebraic approach to the CSP, we introduce a new natural algebraic condition, stable probability distributions on symmetric polymorphisms of a constraint language, and show that the presence of such distributions on polymorphisms of each arity is necessary and sufficient for the finiteness of the integrality gap for the basic LP relaxation of Min CSP(Γ). We also show how stable distributions on symmetric polymorphisms can in principle be used to round solutions of the basic LP relaxation, and how, for several examples that cover all previously known cases, this leads to efficient constant-factor approximation algorithms for Min CSP(Γ). Finally, we show that the absence of another condition, which is implied by stable distributions, leads to NP-hardness of constant-factor approximation.
dc.description.sponsorship The first two authors are supported by UK EPSRC grant EP/J000078/01. The first author is also supported by MICCIN grant TIN2013-48031-C4-1.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher SIAM (Society for Industrial and Applied Mathematics)
dc.relation.ispartof Twenty-sixth annual ACM-SIAM symposium on Discrete algorithms; 2015 Jan 4-6; San Diego, CA. Philadelphia (PA): SIAM; 2015. p. 847-57.
dc.rights © Society for Industrial and Applied Mathematics
dc.subject.other Algorismes
dc.title Towards a characterization of constant-factor approximable Min CSPs
dc.type info:eu-repo/semantics/conferenceObject
dc.identifier.doi http://dx.doi.org/10.1137/1.9781611973730.58
dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN2013-48031-C4-1
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/publishedVersion


This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account

Statistics

Compliant to Partaking