Random sampling and approximation of MAX-CSPs

Noga Alon, W. Fernandez De La Vega, Ravi Kannan, Marek Karpinski

Research output: Contribution to journalArticle

51 Scopus citations

Abstract

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 qr/nr 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.

Original languageEnglish (US)
Pages (from-to)212-243
Number of pages32
JournalJournal of Computer and System Sciences
Volume67
Issue number2
DOIs
StatePublished - Sep 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Random sampling and approximation of MAX-CSPs'. Together they form a unique fingerprint.

  • Cite this