Complexity and Approximability of Parameterized MAX-CSPs

被引：2

作者：

Dell, Holger ^{[1
,2
]}

Kim, Eun Jung ^{[3
]}

Lampis, Michael ^{[3
]}

Mitsou, Valia ^{[4
]}

Moemke, Tobias ^{[1
]}

机构：

[1] Saarland Univ, Saarbrucken, Germany

[2] Cluster Excellence, Saarbrucken, Germany

[3] Univ Paris 09, Paris, France

[4] Hungarian Acad Sci, SZTAKI, Budapest, Hungary

来源：

ALGORITHMICA | 2017年 / 79卷 / 01期

关键词：

Constraint satisfaction problems; Parameterized complexity; Approximation; Clique width; Neighborhood diversity; SATISFIABILITY; HALFSPACES;

D O I：

10.1007/s00453-017-0310-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 , and with various parameters k, and we attempt to fully classify them into the following three cases:The exact optimum can be computed in time. It is -hard to compute the exact optimum, but there is a randomized approximation scheme (), which computes a -approximation in time . There is no unless .

引用

页码：230 / 250

页数：21

共 35 条

[1] SATISFIABILITY, BRANCH-WIDTH AND TSEITIN TAUTOLOGIES [J].