Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorBazgan, Cristina
dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-04-05T13:39:31Z
dc.date.available2011-04-05T13:39:31Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5913
dc.language.isoenen
dc.subjectapproximability
dc.subjectcompleteness
dc.subject.ddc003en
dc.titleCompleteness in differential approximation classes
dc.typeCommunication / Conférence
dc.description.abstractenWe 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. The main classes considered are DAPX, the differential counterpart of APX, including the NP optimization problems approximable in polynomial time within constant differential approximation ratio and the DGLO, the differential counterpart of GLO, including problems for which their local optima guarantee constant differential approximation ratio. We define natural approximation preserving reductions and prove completeness results for the class of the NP optimization problems (class NPO), as well as for DAPX and for a natural subclass of DGLO. 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, the class of NPO problems solvable by polynomial time differential approximation schemata.
dc.identifier.citationpages179-188
dc.relation.ispartoftitleMathematical Foundations of Computer Science 2003 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings
dc.relation.ispartofeditorVojtas, Peter
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2003
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-40671-6
dc.relation.confcountrySLOVAKIA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:22:34Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record