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

Marek Karpinski

Gerhard Woeginger

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.

- Introduction
- Graph Theory
- Network Design
- Sets and Partitions
- Storage and Retrieval
- Sequencing and Scheduling
- Mathematical Programming
- Algebra and Number Theory
- Games and Puzzles
- Logic
- Automata and Language Theory
- Program Optimization
- Miscellaneous
- Bibliography
- Index
- About this document ...