Structure in Approximation Classes
Pierluigi Crescenzi, Viggo Kann, TREVISAN L., Riccardo Silvestri · IRIS Research product catalog (Sapienza University of Rome) · 1999
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. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. 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 asmany 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.