Random sampling and approximation of MAX-CSPs

摘要

In a maximum-r-constraint satisfaction problem with variables {x1,x2,…,xn}, we are given Boolean functions f1,f2,…,fm each involving r of the n variables and are to find the maximum number of these functions that can be made true by a truth assignment to the variables. We show that for r fixed, there is an integer q∈O(log(1/ε)/ε4) such that if we choose q variables (uniformly) at random, the answer to the sub-problem induced on the chosen variables is, with high probability, within an additive error of εqr of qrnr times the answer to the original n-variable problem. The previous best result for the case of r=2 (which includes many graph problems) was that there is an algorithm which given the induced sub-problem on q=O(1/ε5) variables, can find an approximation to the answer to the whole problem within additive error εn2. For r⩾3, the conference version of this paper (in: Proceedings of the 34th ACM STOC, ACM, New York, 2002, pp. 232–239) and independently Andersson and Engebretsen give the first results with sample complexity q dependent only polynomially upon 1/ε. Their algorithm has a sample complexity q of O(1/ε7). They (as also the earlier papers) however do not directly prove any relation between the answer to the sub-problem and the whole problem as we do here. Our method also differs from other results in that it is linear algebraic, rather than combinatorial in nature.