• 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

Completeness in differential approximation classes

Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2005), Completeness in differential approximation classes, International Journal of Foundations of Computer Science, 16, 6, p. 1267-1295

View/Open
cahier204.pdf (519.7Kb)
Type
Article accepté pour publication ou publié
Date
2005
Journal name
International Journal of Foundations of Computer Science
Volume
16
Number
6
Publisher
World Scientific
Pages
1267-1295
Metadata
Show full item record
Author(s)
Ausiello, Giorgio
Bazgan, Cristina
Demange, Marc
Paschos, Vangelis
Abstract (EN)
We study completeness in differential approximability classes. In differential approximation, the quality of an approximation algorithm is the measure of both how far is the solution computed from a worst one and how close is it to an optimal one. We define natural reductions preserving approximation and prove completeness results for the class of the NP optimization problems (class NPO), as well as for DAPX, the differential counterpart of APX, and for a natural subclass of DGLO, the differential counterpart of GLO. We also define class 0-APX of the NPO problems that are not differentially approximable within any ratio strictly greater than 0 unless P = NP. This class is very natural for differential approximation, although has no sense for the standard one. Finally, we prove the existence of hard problems for a subclass of DPTAS, the differential counterpart of PTAS.
Subjects / Keywords
Completeness; Approximation algorithm; Approximation class; Complexity

Related items

Showing items related by title and author.

  • Thumbnail
    Completeness in differential approximation classes 
    Ausiello, Giorgio; Bazgan, Cristina; Demange, Marc; Paschos, Vangelis (2003) Communication / Conférence
  • 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
    Poly-APX- and PTAS-completeness in standard and differential approximation 
    Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2004) Communication / Conférence
  • Thumbnail
    Algorithms for the on-line quota traveling salesman problem 
    Ausiello, Giorgio; Demange, Marc; Laura, Luigi; Paschos, Vangelis (2004) Article accepté pour publication ou publié
  • Thumbnail
    Algorithms for the on-line quota traveling salesman problem 
    Ausiello, Giorgio; Demange, Marc; Laura, Luigi; Paschos, Vangelis (2004) Communication / Conférence
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