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 >>>

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 >>>