#
A compendium of NP optimization problems

**
Pierluigi Crescenzi
**
,
*
piluc@dsi.uniroma1.it
*
and
**
Viggo Kann
**
,
*
viggo@nada.kth.se
*

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.
Springer-Verlag, 1997/1998
*

The latest version of the compendium is available on WWW at
http://www.nada.kth.se/theory/compendium/
.
There you will also find WWW forms to report new problems,
new results on existing problems and errors.

###
Abstract:

*
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.
*

*
Viggo Kann
*

Mon Apr 21 13:07:14 MET DST 1997