The last few years have seen an extremely prolific research activity in the field of design and analysis of approximation algorithms. Actually, the notion of approximation algorithms have been considered since the very beginning of the theory of NP-completeness as a way of coping with the difficulty of solving NP-hard combinatorial optimization problems. For an account of the development of the field, see [10].
The number of both positive and negative results regarding the approximability properties of NP-hard combinatorial problems has continuously increased with an ``exponential'' growth rate. And it does not seem to decline. Currently, there is basically no conference or workshop in the field of algorithms and complexity that does not include in its proceedings at least two or three papers regarding the design of approximation algorithms. As a consequence, the number of problems for which approximation algorithms and/or non-approximability results have been obtained has drastically increased in the last seven years. Moreover, the degree of approximability of several important problems (mostly contained in the appendix of the book by Garey and Johnson [6]) has changed very rapidly. One single example: MAXIMUM 2-SATISFIABILITY started from the 2-approximation algorithm of Johnson [9] and in a few years reached the incredible 1.0741-approximation algorithm of Feige and Goemans [5] (which is almost the best possible performance ratio obtainable for this problem [7]).
Following this rapid development is thus becoming a hard task. This is the main motivation for collecting the existing approximation results into a compendium available to all researchers working (or starting to work) in this field. This paper describes such a compendium, and specifies how the compendium is consultable (and modifiable) on the world wide web.