Poly-APX- and PTAS-completeness in standard and differential approximation
Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis (2004), Poly-APX- and PTAS-completeness in standard and differential approximation, in Trippen, Gerhard, ISAAC'04 :15th International Symposium, Springer : Berlin Heidelberg, p. 124-136. 10.1007/978-3-540-30551-4_13
TypeCommunication / Conférence
Book titleISAAC'04 :15th International Symposium
Book authorTrippen, Gerhard
MetadataShow full item record
Abstract (EN)We first prove the existence of natural Poly-APX-complete problems, for both standard and differential approximation paradigms, under already defined and studied suitable approximation preserving reductions. Next, we devise new approximation preserving reductions, called FT and DFT, respectively, and prove that, under these reductions, natural problems are PTAS-complete, always for both standard and differential approximation paradigms. To our knowledge, no natural problem was known to be PTAS-complete and no problem was known to be Poly-APX-complete until now. We also deal with the existence of intermediate problems under FT- and DFT-reductions and we show that such problems exist provided that there exist NPO-intermediate problems under Turing-reduction. Finally, we show that min coloring is APX-complete for the differential approximation.
Subjects / KeywordsPoly-APX-complete problems; approximation paradigms
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é