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 n^r.We prove a new
general paradigm in that it suffices, for a given set of constraints,
to pick a small uniformly random ... more >>>

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>