Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-17T13:26:54Z
dc.date.available2010-03-17T13:26:54Z
dc.date.issued2005
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3724
dc.language.isoenen
dc.subjectReduction
dc.subjectComplexity
dc.subjectCompleteness
dc.subjectApproximation algorithm
dc.subjectCombinatorial optimization
dc.subjectApproximation schema
dc.subject.ddc003en
dc.titleCompleteness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenSeveral 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.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol339
dc.relation.isversionofjnlissue2-3
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages272-292
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2005.03.007
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-05T14:47:26Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record