Completeness in approximation classes beyond APX
Paschos, Vangelis; Escoffier, Bruno (2006), Completeness in approximation classes beyond APX, Theoretical Computer Science, 359, 1-3, p. 369-377. http://dx.doi.org/10.1016/j.tcs.2006.05.023
TypeArticle accepté pour publication ou publié
Journal nameTheoretical Computer Science
MetadataShow full item record
Abstract (EN)We present a reduction that allows us to establish completeness results for several approximation classes mainly beyond APX. Using it, we extend one of the basic results of S. Khanna, R. Motwani, M. Sudan, and U. Vazirani (On syntactic versus computational views of approximability, SIAM J. Comput. 28 (1998) 164–191) by proving sufficient conditions for getting complete problems for the whole Log-APX, the class of problems approximable within ratios that are logarithms of the size of the instance, as well as for any approximability class beyond APX. We also introduce a new approximability class, called Poly-APX(Δ), dealing with graph-problems approximable with ratios functions of the maximum degree Δ of the input-graph. For this class also, using the proposed reduction, we establish complete problems.
Subjects / KeywordsComplexity; NP-optimization problems; Polynomial approximation; Reductions; Completeness
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é