We consider the problem MAX CSP over multi-valued domains with variables ranging over sets of size s i s and constraints involving k j 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 s 1-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
where s 1 and s 2 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 s 1-k /e in general, and greater than s 1-k (1 -(s -1)/2(k -1)) for s k -1, thus close to the s 1-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/4s 1 + 1/4s 2 over constraints with set sizes s 1 and s 2 , 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.