Show simple item record

dc.contributor.authorLeeuwen, Erik Jan vaneng
dc.contributor.authorLeeuwen, Jan vaneng
dc.date.accessioned2012-02-08T10:35:14Z
dc.date.available2012-02-08T10:35:14Z
dc.date.issued2011-10-14eng
dc.identifier.issn1432-4350en_US
dc.identifier.urihttps://hdl.handle.net/1956/5602
dc.description.abstractApproximation schemes are commonly classified as being either a polynomial-time approximation scheme (ptas) or a fully polynomial-time approximation scheme (fptas). To properly differentiate between approximation schemes for concrete problems, several subclasses have been identified: (optimum-)asymptotic schemes (ptas∞, fptas∞), efficient schemes (eptas), and size-asymptotic schemes. We explore the structure of these subclasses, their mutual relationships, and their connection to the classic approximation classes. We prove that several of the classes are in fact equivalent. Furthermore, we prove the equivalence of eptas to so-called convergent polynomial-time approximation schemes. The results are used to refine the hierarchy of polynomial-time approximation schemes considerably and demonstrate the central position of eptas among approximation schemes. We also present two ways to bridge the hardness gap between asymptotic approximation schemes and classic approximation schemes. First, using notions from fixed-parameter complexity theory, we provide new characterizations of when problems have a ptas or fptas. Simultaneously, we prove that a large class of problems (including all MAX-SNP-complete problems) cannot have an optimum-asymptotic approximation scheme unless P=NP, thus strengthening results of Arora et al. (J. ACM 45(3):501–555, 1998). Secondly, we distinguish a new property exhibited by many optimization problems: pumpability. With this notion, we considerably generalize several problem-specific approaches to improve the effectiveness of approximation schemes with asymptotic behavior.en_US
dc.language.isoengeng
dc.publisherSpringeren_US
dc.rightsCreative Commons Attribution Noncommercial License
dc.rights.urihttps://creativecommons.org/licenses/by-nc/2.0
dc.subjectPolynomial-time approximation schemeseng
dc.subjectAsymptotic polynomial-time approximation schemeseng
dc.subjectApproximation-preserving reductionseng
dc.subjectEPTASeng
dc.subjectNP-optimization problemseng
dc.titleStructure of Polynomial-Time Approximationen_US
dc.typePeer reviewed
dc.typeJournal article
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright The Author(s) 2011en_US
dc.identifier.doihttps://doi.org/10.1007/s00224-011-9366-z
dc.identifier.cristin932451
dc.source.journalTheory of Computing Systems
dc.source.pagenumber641-674
dc.subject.nsiVDP::Mathematics and natural science: 400::Information and communication science: 420::Algorithms and computability theory: 422en_US
dc.subject.nsiVDP::Technology: 500::Information and communication technology: 550::Computer technology: 551en_US
dc.identifier.citationTheory of Computing Systems 50(4): 641-674
dc.source.volume50
dc.source.issue4


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Creative Commons Attribution Noncommercial License
Except where otherwise noted, this item's license is described as Creative Commons Attribution Noncommercial License