期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
