A compendium of NP optimization problems

Editors:

Pierluigi Crescenzi, and Viggo Kann

Subeditors:

Magnús Halldórsson
Graph Theory: Covering and Partitioning, Subgraphs and Supergraphs, Sets and Partitions.
Marek Karpinski
Graph Theory: Vertex Ordering, Network Design: Cuts and Connectivity.
Gerhard Woeginger
Sequencing and Scheduling.

This compendium of approximability results for NP optimization problems was last updated in 2000.

The compendium is also a part of the book Complexity and Approximation.

There is a paper describing how the compendium is used.

We have collected some links to other lists of results.