next up previous index
Next: Introduction   Index

A compendium of NP optimization problems

Pierluigi Crescenzi, and Viggo Kann
Magnús Halldórsson (retired)
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 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 or errors.

There is a paper describing how the compendium is used.

We have collected some links to other lists of results.

Viggo Kann
July 2005