ECCC-Report TR01-100https://eccc.weizmann.ac.il/report/2001/100Comments and Revisions published for TR01-100en-usFri, 14 Dec 2001 11:19:18 +0200
Paper TR01-100
| Random Sampling and Approximation of MAX-CSP Problems |
Noga Alon,
Wenceslas Fernandez de la Vega,
Ravi Kannan,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2001/100We 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 n^r.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) an approximation to the optimum of the whole system up to
an additive error of \epsilon n^r. 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.
Fri, 14 Dec 2001 11:19:18 +0200https://eccc.weizmann.ac.il/report/2001/100