A compendium of NP optimization problems
This is a preliminary version (April 1997) of the catalog of NP optimization
problems. Please send any comment or suggestion to one of the two authors.
A printed version of the compendium will appear in:
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V.,
Marchetti Spaccamela, A., and Protasi, M.,
Approximate solution of NP-hard optimization problems.
The latest version of the compendium is available on WWW at
There you will also find WWW forms to report new problems,
new results on existing problems and errors.
Due to the fact that no NP-complete problem can be solved in
polynomial time (unless P=NP), many approximability results (both
positive and negative) of NP-hard optimization problems have appeared
in the technical literature. In this compendium, we collect a large
number of these results.
Mon Apr 21 13:07:14 MET DST 1997