Polynomial approximation algorithms with performance guarantees: An introduction-by-example

We present a short overview on polynomial approximation of NP-hard problems. We present the main approximability classes together with examples of problems belonging to them. We also describe the general concept of approximability preserving reductions together with a discussion about their capacities and their limits. Finally, we present a quick description of what it is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled. (c) 2004 Elsevier B.V. All rights reserved.