Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOUNDED OCCURRENCE:
Reports tagged with bounded occurrence:
TR99-039 | 24th September 1999
Johan HÃ¥stad

On approximating CSP-B

We prove that any constraint satisfaction problem
where each variable appears a bounded number of
times admits a nontrivial polynomial time approximation
algorithm.

more >>>



ISSN 1433-8092 | Imprint