• 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 standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness

Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2005), Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, 339, 2-3, p. 272-292. http://dx.doi.org/10.1016/j.tcs.2005.03.007

View/Open
cahier217.pdf (445.8Kb)
Type
Article accepté pour publication ou publié
Date
2005
Journal name
Theoretical Computer Science
Volume
339
Number
2-3
Publisher
Elsevier
Pages
272-292
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2005.03.007
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Escoffier, Bruno
Paschos, Vangelis
Abstract (EN)
Several problems are known to be APX-, DAPX-, PTAS-, or Poly-APX-PB-complete under suitably defined approximation-preserving reductions. But, to our knowledge, no natural problem is known to be PTAS-complete and no problem at all is known to be Poly-APX-complete. On the other hand, DPTAS- and Poly-DAPX-completeness have not been studied until now. We first prove in this paper the existence of natural Poly-APX- and Poly-DAPX-complete problems under the well known PTAS-reduction and under the DPTAS-reduction (defined in “G. Ausiello, C. Bazgan, M. Demange, and V. Th. Paschos, Completeness in differential approximation classes, MFCS’03”), respectively. Next, we deal with PTAS- and DPTAS-completeness. We introduce approximation preserving reductions, called FT and DFT, respectively, and prove that, under these new reductions, natural problems are PTAS-complete, or DPTAS-complete. Then, we deal with the existence of intermediate problems under our reductions and we partially answer this question showing that the existence of NPO-intermediate problems under Turing-reductions is a sufficient condition for the existence of intermediate problems under both FT- and DFT-reductions. Finally, we show that MIN COLORING is DAPX-complete under DPTAS-reductions. This is the first DAPX-complete problem that is not simultaneously APX-complete.
Subjects / Keywords
Reduction; Complexity; Completeness; Approximation algorithm; Combinatorial optimization; Approximation schema

Related items

Showing items related by title and author.

  • Thumbnail
    Poly-APX- and PTAS-completeness in standard and differential approximation 
    Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2004) Communication / Conférence
  • 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
    Completeness in approximation classes beyond APX 
    Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation for satisfiability and related problems 
    Bazgan, Cristina; Paschos, Vangelis (2003) 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