A combinatorial algorithm for max csp |
| |
Authors: | Mayur Datar Rajeev Motwani Rina Panigrahy |
| |
Affiliation: | Department of Computer Science, Gates 4B, Stanford University, Stanford, CA 94305-9045, USA |
| |
Abstract: | 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 , 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 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 . This shows that our analysis is tight for any method that uses the linear programming upper bound. |
| |
Keywords: | Algorithmical approximation Analysis of algorithms Combinatorial problems Databases Design of algorithms Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|