P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan.
Structure in Approximation Classes.
In Proceedings of the 1st Combinatorics and Computing Conference.
LNCS 959, Springer Verlag, pages 539-548, 1995.
Also Technical Report SI/RR-95/07, Dip. di Scienze dell'Informazione, Universita' di Roma ``La Sapienza'', 1995.
We study the structure of classes of optimization problems, such as NPO (the class of optimization problems whose underlying decision problem is in NP) and APX (the class of constant-factor approximable NPO problems). In particular, we give the first examples of natural APX-intermediate problems (Bin Packing, Edge Coloring, and Min Degree Spanning Tree) and of natural NPO-complete problems. Moreover, we state new connections between the approximability and the query complexity of NPO problems and we solve an open question about the aproximability of the Max Clique problem.