• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Complexity and Approximability of Parameterized MAX-CSPs

Thumbnail
Date
2017
Link to item file
https://arxiv.org/abs/1511.05546v2
Dewey
Programmation, logiciels, organisation des données
Sujet
Constraint satisfaction problems; Parameterized complexity; Approximation; Clique width; Neighborhood diversity
Journal issue
Algorithmica
Volume
79
Number
1
Publication date
09-2017
Article pages
230-250
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s00453-017-0310-8
URI
https://basepub.dauphine.fr/handle/123456789/19103
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Dell, Holger
162754 Universität des Saarlandes
Kim, Eun Jung
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia
220549 Institute for Computer Science and Control [Budapest] [SZTAKI]
Mömke, Tobias
162754 Universität des Saarlandes
Type
Article accepté pour publication ou publié
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 Open image in new window-hard to compute the exact optimum, but there is a randomized FPT approximation scheme ( FPT\text {-}AS ), which computes a (1−ϵ) -approximation in time f(k,ϵ)⋅poly(n) . 3.There is no FPT\text {-}AS unless Open image in new window. For the corresponding standard CSPs, we establish FPT versus Open image in new window-hardness results.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.