next up previous
Next: How is the compendium Up: How to find the Previous: Introduction

A compendium of NP optimization problems

In 1993 the two authors of this paper started to collect approximation results. We soon noticed that the amount of approximability results was enormous, and therefore we had to limit ourselves to considering polynomial time approximation results for NP optimization problems that are not solvable optimally in polynomial time. This means that we considered neither approximation algorithms for #P-hard or PSPACE-hard problems, nor fast approximation algorithms for polynomially solvable problems such as MAXIMUM MULTICOMMODITY FLOW. We of course collected the best upper and lower bounds of approximation, but we did not try to find the fastest approximation algorithm giving the best approximation upper bound - any polynomial time algorithm sufficed.

With these restrictions, in 1994 we made the first version of the compendium available as a Postscript file via anonymous ftp, and announced it in the news group comp.theory. The response from the research community was fortunately enough extensive, and we received both corrections, updated results and results for new problems. Since then we have made several revisions of the compendium, and the current version has number eight. In Section 6 we explain how you can help us to improve the compendium.

We noted early that a Postscript file is not the ideal medium for the compendium. A researcher is often only interested in looking up the results for a single problem. At the end of 1994 we therefore constructed a web version of the compendium, containing exactly the same text as the Postscript file, but with hypertext links between the different sections and problems, making it a lot easier to use. Recently, we have also added links from the bibliography to papers that are available electronically. In Section 4 some statistics for the use are presented.


next up previous
Next: How is the compendium Up: How to find the Previous: Introduction
Viggo Kann
1998-10-31