Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663718 | European Journal of Operational Research | 2005 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Marc Demange, Vangelis Th. Paschos,