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