In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. It is known that every Boolean (that is, two-valued) Max CSP problem with a finite set of allowed constraint types is either solvable exactly in polynomial time or else APX-complete (and hence can have no polynomial time approximation scheme unless P=NP. It has been an open problem for several years whether this result can be extended to non-Boolean Max CSP, which is much more difficult to analyze than the Boolean case. In this paper, we make the first step in this direction by establishing this result for Max CSP over a three-element domain. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known algebraic combinatorial property of supermodularity. We also show that every hard three-valued Max CSP problem contains, in a certain specified sense, one of the two basic hard Max CSP problems which are the Maximum k-colourable subgraph problems for k=2,3.
The Max-CSP framework has been well-studied in the Boolean case. Many fundamental results have been obtained, concerning both complexity classifications and approximation properties (see, e.g., @cite_18 @cite_21 @cite_8 @cite_3 @cite_2 @cite_26 ). In the non-Boolean case, a number of results have been obtained that concern exact (superpolynomial) algorithms or approximation properties (see, e.g., @cite_5 @cite_1 @cite_0 @cite_10 ). The main research problem we will look at in this paper is the following.
@cite_18 @cite_26 @cite_8 @cite_21 @cite_1 @cite_3 @cite_0 @cite_2 @cite_5 @cite_10
2097646889 2084350425 2068190866 22128777
By the breakthrough work of Hastad [J ACM 48(4) (2001), 798–859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin, and Max E4-Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2-CSP); as a corollary of the celebrated Goemans-Williamson algorithm [J ACM 42(6) (1995), 1115–1145], we know that every Boolean 2-CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2-CSPs over larger, non-Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2-SAT to domains of size d, can be approximated to a factor better than (1 − 1 d2). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not-All-Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d ≥ 3. In the Boolean case, Not-All-Equal Sat with three variables per constraint is equivalent to Max 2-SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2-SAT can be reduced to Not-All-Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2-CSPs called regular 2-CSPs can all be approximated beyond their random assignment threshold. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004 We consider the problem MAX CSP over multi-valued domains with variables ranging over sets of size si ≤ s and constraints involving kj ≤ k variables. We study two algorithms with approximation ratios A and B. respectively, so we obtain a solution with approximation ratio max (A, B).The first algorithm is based on the linear programming algorithm of Serna, Trevisan, and Xhafa [Proc. 15th Annual Symp. on Theoret. Aspects of Comput. Sci., 1998, pp. 488-498] and gives ratio A which is bounded below by s1-k. For k = 2, our bound in terms of the individual set sizes is the minimum over all constraints involving two variables of (1 2√s1+ 1 2√s2)2, where s1 and s2 are the set sizes for the two variables.We then give a simple combinatorial algorithm which has approximation ratio B, with B > A e. The bound is greater than s1-k e in general, and greater than s1-k(1 - (s - 1) 2(k - 1)) for s ≤ k - 1, thus close to the s1-k linear programming bound for large k. For k = 2, the bound is 4 9 if s = 2, 1 2(s - 1) if s ≥ 3, and in general greater than the minimum of 1 4S1 + 1 4s2 over constraints with set sizes s1 and s2, thus within a factor of two of the linear programming bound.For the case of k = 2 and s = 2 we prove an integrality gap of 4 9 (1 + O(n-1 2)). This shows that our analysis is tight for any method that uses the linear programming upper bound. We study optimization problems that may be expressed as "Boolean constraint satisfaction problems." An instance of a Boolean constraint satisfaction problem is given by m constraints applied to n Boolean variables. Different computational problems arise from constraint satisfaction problems depending on the nature of the "underlying" constraints as well as on the goal of the optimization task. Here we consider four possible goals: Max CSP (Min CSP) is the class of problems where the goal is to find an assignment maximizing the number of satisfied constraints (minimizing the number of unsatisfied constraints). Max Ones (Min Ones) is the class of optimization problems where the goal is to find an assignment satisfying all constraints with maximum (minimum) number of variables set to 1. Each class consists of infinitely many problems and a problem within a class is specified by a finite collection of finite Boolean functions that describe the possible constraints that may be used. Tight bounds on the approximability of every problem in Max CSP were obtained by Creignou [ J. Comput. System Sci., 51 (1995), pp. 511--522]. In this work we determine tight bounds on the "approximability" (i.e., the ratio to within which each problem may be approximated in polynomial time) of every problem in Max Ones, Min CSP, and Min Ones. Combined with the result of Creignou, this completely classifies all optimization problems derived from Boolean constraint satisfaction. Our results capture a diverse collection of optimization problems such as MAX 3-SAT, Max Cut, Max Clique, Min Cut, Nearest Codeword, etc. Our results unify recent results on the (in-)approximability of these optimization problems and yield a compact presentation of most known results. Moreover, these results provide a formal basis to many statements on the behavior of natural optimization problems that have so far been observed only empirically. Given an instance @math of a CSP, a tester for @math distinguishes assignments satisfying @math from those which are far from any assignment satisfying @math . The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize the hardness of testing Boolean CSPs in terms of the algebra generated by the relations used to form constraints. In terms of computational complexity, we show that if a non-trivial Boolean CSP is sublinear-query testable (resp., not sublinear-query testable), then the CSP is in NL (resp., P-complete, ⊕L-complete or NL-complete) and that if a sublinear-query testable Boolean CSP is constant-query testable (resp., not constant-query testable), then counting the number of solutions of the CSP is in P (resp., @math P-complete). Also, we conjecture that a CSP instance is testable in sublinear time if its Gaifman graph has bounded treewidth. We confirm the conjecture when a near-unanimity operation is a polymorphism of the CSP.