• 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

A Survey on the Structure of Approximation Classes

Paschos, Vangelis; Escoffier, Bruno (2010), A Survey on the Structure of Approximation Classes, Computer Science Review, 4, 1, p. 19-40. http://dx.doi.org/10.1016/j.cosrev.2009.11.001

View/Open
cahierLamsade267.pdf (580.5Kb)
Type
Article accepté pour publication ou publié
Date
2010
Journal name
Computer Science Review
Volume
4
Number
1
Publisher
Elsevier
Pages
19-40
Publication identifier
http://dx.doi.org/10.1016/j.cosrev.2009.11.001
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Escoffier, Bruno
Abstract (EN)
The structure of approximability classes by the introduction of approximation preserving reductions has been one of the main research programmes in theoretical computer science during the last thirty years. This paper surveys the main results achieved in this domain.
Subjects / Keywords
Approximation classes

Related items

Showing items related by title and author.

  • Thumbnail
    Structures des classes d'approximation : un état de l'art 
    Escoffier, Bruno; Paschos, Vangelis (2007) Document de travail / Working paper
  • Thumbnail
    Completeness in approximation classes beyond APX 
    Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié
  • Thumbnail
    Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness 
    Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2005) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
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