Optimal Vertex Sampling for Constraint Satisfaction ProblemsResearch Paper
How many variables of a constraint satisfaction problem must be inspected to estimate its optimum? The natural estimator picks of the variables uniformly at random, solves the subproblem induced on them, and multiplies its optimum by , where is the arity. This estimator underlies the approximation schemes for dense instances (Arora–Karger–Karpin…