next up previous
Next: Introduction

How to find the best approximation results
- a follow-up to Garey and Johnson1

Pierluigi Crescenzi2 - Viggo Kann3


A compendium of NP optimization problems, containing the best approximation results known for each problem, is available on the world wide web at
In this paper we describe the compendium, and specify how the compendium is consultable as well as modifiable on the web. We also give statistics for the use of the compendium.

Viggo Kann