Quaderni di Matematica

Various results on the properties of NP-complete optimization problems and on the characterization of these problems either with respect to their approximation properties or with respect to their combinatorial strutture have been presented in the literature.
In particular the authors have considered the approaches given by Paz and Moran (1977) and by Garey and Johnson (1978) because of the interest of their results.
These papers, are, without any doubt, very interesting and new results of remarkable importance have been captured. Nevertheless, it seems to lack an attempt of organizing all these results in a unified framework as general as possible.