• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2006
Journal name
European Journal of Operational Research
Volume
172
Number
3
Publisher
Elsevier
Pages
719-739
Publication identifier
http://dx.doi.org/10.1016/j.ejor.2005.06.006
Metadata
Show full item record
Author(s)
Ausiello, Giorgio
Paschos, Vangelis
Abstract (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 optimization

Related items

Showing items related by title and author.

  • Thumbnail
    Reductions that preserve approximability 
    Paschos, Vangelis; Ausiello, Giorgio (2007) Chapitre d'ouvrage
  • Thumbnail
    Completeness in differential approximation classes 
    Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2005) Article accepté pour publication ou publié
  • Thumbnail
    Completeness in differential approximation classes 
    Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2003) Communication / Conférence
  • Thumbnail
    On-line models for set-covering: the power of greediness 
    Ausiello, Giorgio; Giannakos, Aristotelis; Paschos, Vangelis (2006) Document de travail / Working paper
  • Thumbnail
    Online models for set-covering: the flaw of greediness 
    Paschos, Vangelis; Giannakos, Aristotelis; Ausiello, Giorgio (2008) Chapitre d'ouvrage
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo