• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
http://arxiv.org/abs/1008.0213v2
Date
2012
Conference title
6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Conference date
2011-09
Conference city
Saarbrücken
Conference country
Germany
Book title
Parameterized and Exact Computation 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
Book author
Marx, Daniel; Rossmanith, Peter
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
7112
Published in
Berlin
ISBN
978-3-642-28049-8
Number of pages
273
Pages
118-131
Publication identifier
10.1007/978-3-642-28050-4_10
Metadata
Show full item record
Author(s)
Kim, Eun Jung
Laboratoire 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 Average

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized algorithms for min-max multiway cut and list digraph homomorphism 
    Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
  • Thumbnail
    A polynomial-time algorithm for Outerplanar Diameter Improvement 
    Cohen, Nathann; Gonçalves, Daniel; Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié
  • Thumbnail
    An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion 
    Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, O-joung; Paul, Christophe (2017) Article accepté pour publication ou publié
  • Thumbnail
    On Exact Algorithms for Permutation CSP 
    Kim, Eun Jung; Gonçalves, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Constructive algorithm for path-width of matroids 
    Jeong, Jisu; Kim, Eun Jung; Oum, Sang-il (2016) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo