next up previous
Next: Bibliography Up: How to find the Previous: The future of the


In this paper we have briefly described a compendium of NP optimization problems that is available on the web. We believe that such a compendium will turn out to be very useful whenever someone has to deal with the approximate solution of an NP-hard optimization problem. Indeed, as stated in [1], ``the first step in proving an inapproximability result for a given problem is to check whether it is already known to be inapproximable.'' The compendium is then the right starting point to perform this test (actually, this is true also for positive results). Moreover, even if the problem at hand is not contained in the compendium, it is likely that it contains other problems that can be reduced to this problem.

We have also described how the compendium can now be updated directly on the web by means of four forms that have been designed to be easy to use. We hope that in this way researchers will be stimulated to help us in maintaining the compendium as up-to-date as possible: the sooner they report a result the sooner it will be publicly known!

Viggo Kann