Random sampling and approximation of MAX-CSP problems

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

Research output: Contribution to journalConference article

28 Scopus citations

Abstract

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error εnr. We prove a new general paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of εnr. Our method gives for the first time a polynomial in ε-1 bound on the sample size necessary to carry out the above approximation. Moreover, this bound is independent in the exponent on the dimension r. The above method gives a completely uniform sampling technique for all the MAX-rCSP problems, and improves the best known sample bounds for the low dimensional problems, like MAX-CUT. The method of solution depends on a new result on the cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. This method could be also of independent interest.

Original languageEnglish (US)
Pages (from-to)232-239
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

All Science Journal Classification (ASJC) codes

  • Software

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

Cite this