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 539548, 1995.
 Note

Also Technical Report SI/RR95/07, Dip. di Scienze dell'Informazione,
Universita' di Roma ``La Sapienza'', 1995.
 Abstract
 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 constantfactor approximable
NPO problems). In particular, we give the first examples of natural
APXintermediate problems (Bin Packing, Edge Coloring, and Min Degree
Spanning Tree) and of
natural NPOcomplete 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.