Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > UMESH VAZIRANI:
All reports by Author Umesh Vazirani:

TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>




ISSN 1433-8092 | Imprint