Show simple item record

dc.contributor.authorKim, Eun Jung*
dc.contributor.authorWilliams, Ryan*
dc.date.accessioned2013-10-14T09:25:00Z
dc.date.available2013-10-14T09:25:00Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11820
dc.language.isoenen
dc.subjectConstraint Satisfaction Problems above Averageen
dc.subject.ddc518en
dc.titleImproved Parameterized Algorithms for above Average Constraint Satisfactionen
dc.typeCommunication / Conférence
dc.description.abstractenFor many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment for Max-E3-Sat allows 7/8-approximation and for every ε > 0 there is no polynomial-time (7/8 + ε)-approximation unless P=NP. Another example is the Permutation CSP of bounded arity. Given the expected fraction ρ of the constraints satisfied by a random assignment (i.e. permutation), there is no (ρ + ε)-approximation algorithm for every ε > 0, assuming the Unique Games Conjecture (UGC). In this work, we consider the following parameterization of constraint satisfaction problems. Given a set of m constraints of constant arity, can we satisfy at least ρm + k constraint, where ρ is the expected fraction of constraints satisfied by a random assignment? Constraint Satisfaction Problems above Average have been posed in different forms in the literature [18,17]. We present a faster parameterized algorithm for deciding whether m/2 + k/2 equations can be simultaneously satisfied over F2 . As a consequence, we obtain O(k)-variable bikernels for boolean CSPs of arity c for every fixed c, and for permutation CSPs of arity 3. This implies linear bikernels for many problems under the “above average” parameterization, such as Max- c -Sat, Set-Splitting, Betweenness and Max Acyclic Subgraph. As a result, all the parameterized problems we consider in this paper admit 2 O(k)-time algorithms. We also obtain non-trivial hybrid algorithms for every Max c-CSP: for every instance I, we can either approximate I beyond the random assignment threshold in polynomial time, or we can find an optimal solution to I in subexponential time.en
dc.identifier.citationpages118-131en
dc.relation.ispartofseriestitleLecture Notes in Computer Scienceen
dc.relation.ispartofseriesnumber7112en
dc.relation.ispartoftitleParameterized and Exact Computation 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papersen
dc.relation.ispartofeditorMarx, Daniel
dc.relation.ispartofeditorRossmanith, Peter
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2012
dc.relation.ispartofpages273en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-28050-4en
dc.identifier.urlsitehttp://arxiv.org/abs/1008.0213v2en
dc.subject.ddclabelModèles mathématiques. Algorithmesen
dc.relation.ispartofisbn978-3-642-28049-8en
dc.relation.conftitle6th International Symposium on Parameterized and Exact Computation, IPEC 2011en
dc.relation.confdate2011-09
dc.relation.confcitySaarbrückenen
dc.relation.confcountryGermanyen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-28050-4_10en
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds*
hal.identifierhal-01496463*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record