Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2001 Copyright 2001 University of Bonn, Department of Computer Science, Abt. V
8976

Dec 17, 2001

Random Sampling and Approximation of MAX-CSP Problems
Noga Alon, W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski
[Download PostScript] [Download PDF]

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 epsilon*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 epsilon*nr. Our method gives for the first time a polynomial in epsilon-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.

Last Change: 11/05/14 at 10:19:37
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V