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
TypeArticle accepté pour publication ou publié
Journal nameInternational Journal of Foundations of Computer Science
MetadataShow full item record
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 / KeywordsCompleteness; Approximation algorithm; Approximation class; Complexity
Showing items related by title and author.
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é