Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-124 | 25th September 2006 00:00

Approximation of Global MAX-CSP Problems

RSS-Feed

Abstract:

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 that class of problems. The method yields also the best up to date sample complexity bound for the balanced MAX-CSP problems such as the graph and hypergraph BISECTION problems.



ISSN 1433-8092 | Imprint