Thumbnail - Request a copy

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

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
Journal name
European Journal of Operational Research
Volume
165
Number
3
Publisher
Elsevier
Pages
555-568
Publication identifier
Metadata
Show full item record
Author(s)
Demange, Marc
Paschos, Vangelis
Abstract (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.
Subjects / Keywords
Traveling salesman; Complexity theory; Computing science; Combinatorial optimization