A compendium of NP optimization problems
Magnús Halldórsson (retired)
Covering and Partitioning,
Subgraphs and Supergraphs,
Sets and Partitions
Cuts and Connectivity.
Sequencing and Scheduling
This is a continuously updated catalog of approximability results
for NP optimization problems. The compendium is also a part of the book
Complexity and Approximation.
The compendium has not been updated for a while, so there might exist
recent results that are not mentioned in the compendium. If you
happen to notice such a missing result, please report it to us
using the web forms.
You can use web forms to report new problems,
new results on existing problems,
updates of references
There is a paper describing how the compendium is used.
We have collected some links to other lists of results.