Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorEscoffier, Bruno
dc.date.accessioned2009-10-07T12:17:36Z
dc.date.available2009-10-07T12:17:36Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2161
dc.language.isoenen
dc.subjectComplexityen
dc.subjectNP-optimization problemsen
dc.subjectPolynomial approximationen
dc.subjectReductionsen
dc.subjectCompletenessen
dc.subject.ddc003en
dc.titleCompleteness in approximation classes beyond APXen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol359en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages369-377en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2006.05.023en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record