Complexity and Approximability of Parameterized MAX-CSPs

Complexity and Approximability of Parameterized MAX-CSPs

0.00 Avg rating0 Votes
Article ID: iaor20173041
Volume: 79
Issue: 1
Start Page Number: 230
End Page Number: 250
Publication Date: Sep 2017
Journal: Algorithmica
Authors: , , , ,
Keywords: programming: constraints, heuristics
Abstract:

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 equ1 , OR equ2 , PARITY equ3 , and MAJORITY equ4 , and with various parameters k, and we attempt to fully classify them into the following three cases:

  • The exact optimum can be computed in FPT time.
  • It is W[I] ‐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 ) .
  • There is no FPTAS unless FPT=W[I].
  • For the corresponding standard CSPs, we establish FPT equ11 versus ‐hardness results.

    Reviews

    Required fields are marked *. Your email address will not be published.