Improved Parameterized Algorithms for above Average Constraint Satisfaction
Kim, Eun Jung; Williams, Ryan (2012), Improved Parameterized Algorithms for above Average Constraint Satisfaction, in Marx, Daniel; Rossmanith, Peter, Parameterized and Exact Computation 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, Springer : Berlin, p. 118-131. 10.1007/978-3-642-28050-4_10
Type
Communication / ConférenceExternal document link
http://arxiv.org/abs/1008.0213v2Date
2012Conference title
6th International Symposium on Parameterized and Exact Computation, IPEC 2011Conference date
2011-09Conference city
SaarbrückenConference country
GermanyBook title
Parameterized and Exact Computation 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected PapersBook author
Marx, Daniel; Rossmanith, PeterPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
7112Published in
Berlin
ISBN
978-3-642-28049-8
Number of pages
273Pages
118-131
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Williams, Ryan
Abstract (EN)
For 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.Subjects / Keywords
Constraint Satisfaction Problems above AverageRelated items
Showing items related by title and author.
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence
-
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence
-
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
-
Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017) Article accepté pour publication ou publié