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.
