ملخص: We consider the problem over multi-valued domains with variables ranging over sets of size sis and constraints involving kjk 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 , 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 sk-1, thus close to the s1-k linear programming bound for large k. For k=2, the bound is if s=2, 1/2(s-1) if s3, 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 . This shows that our analysis is tight for any method that uses the linear programming upper bound.

لغة: إنجليزية
الموضوع الإعلام الآلي

الكلمات الدالة:
Graph algorithms
Databases
Combinatorial problems
Design of algorithms
Algorithmical approximation
Analysis of algorithms