Reductions, completeness and the hardness of approximability
Ausiello, Giorgio; Paschos, Vangelis (2006), Reductions, completeness and the hardness of approximability, European Journal of Operational Research, 172, 3, p. 719-739. http://dx.doi.org/10.1016/j.ejor.2005.06.006
Type
Article accepté pour publication ou publiéDate
2006Journal name
European Journal of Operational ResearchVolume
172Number
3Publisher
Elsevier
Pages
719-739
Publication identifier
Metadata
Show full item recordAbstract (EN)
In computability and in complexity theory reductions are widely used for mapping sets into sets in order to prove undecidability or hardness results. In the study of the approximate solvability of hard discrete optimization problems, suitable kinds of reductions, called approximation preserving reductions, can also be used to transfer from one problem to another either positive results (solution techniques) or negative results (non-approximability results). In this paper various kinds of approximation preserving reductions are surveyed and their properties discussed. The role of completeness under approximation preserving reductions is also analyzed and its relationship with hardness of approximability is explained.Subjects / Keywords
Completeness in approximation classes; Approximation preserving reduction; Polynomial approximation; NP-hard optimization problems; Computing science; Complexity theory; Combinatorial optimizationRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Ausiello, Giorgio (2007) Chapitre d'ouvrage
-
Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
-
Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2003) Communication / Conférence
-
Ausiello, Giorgio; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Ausiello, Giorgio; Escoffier, Bruno; Monnot, Jérôme; Paschos, Vangelis (2006) Communication / Conférence