Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ravi Kannan:

TR06-124 | 25th September 2006
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Approximation of Global MAX-CSP Problems

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

TR01-100 | 14th December 2001
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Random Sampling and Approximation of MAX-CSP Problems

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

ISSN 1433-8092 | Imprint