CD Book Algorithms

A compendium of NP optimization problems

Pierluigi Crescenzi , and Viggo Kann ,

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

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997