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

Demange, Marc; Paschos, Vangelis

Demange, Marc; Paschos, Vangelis (2005), Polynomial approximation algorithms with performance guarantees: an introduction-by-example, European Journal of Operational Research, 165, 3, p. 555-568. http://dx.doi.org/10.1016/j.ejor.2004.03.021

Type

Article accepté pour publication ou publié

Date

2005

Nom de la revue

European Journal of Operational Research

Volume

165

Numéro

Éditeur

Elsevier

Pages

555-568

Résumé (EN)

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.

Mots-clés

Traveling salesman; Complexity theory; Computing science; Combinatorial optimization