• 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 - Request a copy

Complexity and Approximability of Parameterized MAX-CSPs

Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015), Complexity and Approximability of Parameterized MAX-CSPs, in Husfeldt, Thore; Kanj, Iyad, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik : Wadern, p. 294-306. 10.4230/LIPIcs.IPEC.2015.294

Type
Communication / Conférence
Date
2015
Conference title
10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Conference date
2015-09
Conference city
Patras
Conference country
Greece
Book title
10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Book author
Husfeldt, Thore; Kanj, Iyad
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Published in
Wadern
ISBN
978-3-939897-92-7
Pages
294-306
Publication identifier
10.4230/LIPIcs.IPEC.2015.294
Metadata
Show full item record
Author(s)
Dell, Holger

Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia
Institute for Computer Science and Control [Budapest] [SZTAKI]
Mömke, Tobias
Abstract (EN)
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable-constraint incidence graph of the CSP instance.We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k, and we attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPTAS), which computes a (1−ϵ)-approximation in time f(k,ϵ)⋅poly(n). 3. There is no FPTAS unless FPT=W[1].For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.
Subjects / Keywords
Parameterized Approximation; Structural Parameters; Constraint Satisfaction

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity and Approximability of Parameterized MAX-CSPs 
    Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017) Article accepté pour publication ou publié
  • Thumbnail
    Token Sliding on Split Graphs 
    Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    Token Sliding on Split Graphs 
    Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Article accepté pour publication ou publié
  • Thumbnail
    Grundy Distinguishes Treewidth from Pathwidth 
    Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Communication / Conférence
  • 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é
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