P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan.<br>
<b>Structure in Approximation Classes</b>.<br>
In <I> Proceedings of the <A 
HREF="http://math.uwaterloo.ca/~mli/cocoon.html">
1st Combinatorics and
Computing Conference</A></I>. <br>
LNCS 959, Springer Verlag, pages 539-548, 1995.<br>






<dl>

<dt> <b> Note </b> 
<dd> 
Also Technical Report SI/RR-95/07, Dip. di Scienze dell'Informazione, 
Universita' di Roma ``La Sapienza'', 1995.


<dt> <b> Abstract </b> <dd> 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.

</dl>