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.
