## Abstract

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 ε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 and with high probability) an approximation to the optimum of the whole system up to an additive error of εn^{r}. Our method gives for the first time a polynomial in ε^{-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.

Original language | English (US) |
---|---|

Pages (from-to) | 232-239 |

Number of pages | 8 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2002 |

Externally published | Yes |

Event | Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada Duration: May 19 2002 → May 21 2002 |

## All Science Journal Classification (ASJC) codes

- Software