Complexity and Approximability of Parameterized MAX-CSPs
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2017), Complexity and Approximability of Parameterized MAX-CSPs, Algorithmica, 79, 1, p. 230-250. 10.1007/s00453-017-0310-8
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1511.05546v2Date
2017Journal name
AlgorithmicaVolume
79Number
1Publisher
Springer
Pages
230-250
Publication identifier
Metadata
Show full item recordAuthor(s)
Dell, HolgerUniversität des Saarlandes
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael

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
Universität des Saarlandes
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.Subjects / Keywords
Constraint satisfaction problems; Parameterized complexity; Approximation; Clique width; Neighborhood diversityRelated items
Showing items related by title and author.
-
Dell, Holger; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Mömke, Tobias (2015) Communication / Conférence
-
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019) Communication / Conférence
-
Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Article accepté pour publication ou publié
-
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Communication / Conférence
-
Kim, Eun Jung; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2017) Article accepté pour publication ou publié