26.09.2006

We study the problem of absolute approximability of MAX-CSP problems withthe global constraints. We prove existence of an efficient sampling methodfor the MAX-CSP class of problems with linear global constraints and boundedfeasibility gap. It gives for the first time a polynomial inε^-1sample complexity bound for that class of problems. The method yields also thebest up to date sample complexity bound for the balanced MAX-CSP problemssuch as the graph and hypergraph BISECTION problems.