Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-066 | 21st November 1996 00:00

Structure in Approximation Classes


Authors: Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
Publication: 13th December 1996 20:26
Downloads: 2317


The study of the approximability properties of NP-hard
optimization problems has recently made great advances mainly due
to the results obtained in the field of proof checking. In a
recent breakthrough the APX-completeness of several important
optimization problems is proved, thus reconciling `two distinct
views of approximation classes: syntactic and computational'.
In this paper we obtain new results on the structure of several
computationally-defined approximation classes. In particular, after
defining a new approximation preserving reducibility to be used
for as many approximation classes as possible, we give the first
examples of natural NPO-complete problems and the first examples
of natural APX-intermediate problems. Moreover, we state new
connections between the approximability properties and the query
complexity of NPO problems.

ISSN 1433-8092 | Imprint