Polynomial-time approximation scheme

In computer science (particularly algorithmics), a '''polynomial-time approximation scheme''' ('''PTAS''') is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).

A PTAS is an algorithm which takes an instance of an optimization problem and a parameter {{math|ε > 0}} and produces a solution that is within a factor {{math|1 + ε}} of being optimal (or {{math|1 – ε}} for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most {{math|(1 + ε)''L''}}, with {{mvar|L}} being the length of the shortest tour.<ref>Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref>

The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time {{math|''O''(''n''{{sup|1/ε}})}} or even {{math|''O''(''n''{{sup|exp(1/ε)}})}} counts as a PTAS.

==Variants== ===Deterministic=== A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is {{math|''O''(''n''{{sup|(1/ε)!}})}}. One way of addressing this is to define the '''efficient polynomial-time approximation scheme''' or '''EPTAS''', in which the running time is required to be {{math|''O''(''n''{{sup|''c''}})}} for a constant {{mvar|c}} independent of {{math|ε}}. This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε is being used; however, the constant under the big-O can still depend on ε arbitrarily. In other words, an EPTAS runs in FPT time where the parameter is ε.

Even more restrictive, and useful in practice, is the '''fully polynomial-time approximation scheme''' or '''FPTAS''', which requires the algorithm to be polynomial in both the problem size {{mvar|n}} and {{math|1/ε}}.

Unless P = NP, it holds that {{nowrap|FPTAS ⊊ PTAS ⊊ APX}}.<ref name=Jansen>{{citation|first=Thomas|last=Jansen|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|pages=5–28|title=Lectures on Proof Verification and Approximation Algorithms|series=Lecture Notes in Computer Science |editor1-first=Ernst W.|editor1-last=Mayr|editor2-first=Hans Jürgen|editor2-last=Prömel|editor3-first=Angelika|editor3-last=Steger|editor3-link=Angelika Steger|publisher=Springer|year=1998|volume=1367 |isbn=9783540642015|doi=10.1007/BFb0053011}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p. 20].</ref> Consequently, under this assumption, APX-hard problems do not have PTASs.

Another deterministic variant of the PTAS is the '''quasi-polynomial-time approximation scheme''' or '''QPTAS'''. A QPTAS has time complexity {{math|''n''{{sup|polylog(''n'')}}}} for each fixed {{math|ε > 0}}. Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme.

===Randomized=== Some problems which do not have a PTAS may admit a randomized algorithm with similar properties, a '''polynomial-time randomized approximation scheme''' or '''PRAS'''. A PRAS is an algorithm which takes an instance of an optimization or counting problem and a parameter {{math|ε > 0}} and, in polynomial time, produces a solution that has a ''high probability'' of being within a factor {{math|ε}} of optimal. Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement is generally greater than 1/2). Like a PTAS, a PRAS must have running time polynomial in {{mvar|n}}, but not necessarily in {{math|ε}}; with further restrictions on the running time in {{math|ε}}, one can define an '''efficient polynomial-time randomized approximation scheme''' or '''EPRAS''' similar to the EPTAS, and a '''fully polynomial-time randomized approximation scheme''' or '''FPRAS''' similar to the FPTAS.<ref name="vvv">{{cite book | last = Vazirani | first = Vijay V. | title = Approximation Algorithms | publisher = Springer | year = 2003 | pages = 294–295 | location = Berlin | isbn = 3-540-65367-8 }}</ref>

==As a complexity class== The term PTAS may also be used to refer to the class of optimization problems that have a PTAS. PTAS is a subset of APX, and unless P = NP, it is a strict subset. <ref name=Jansen></ref>

Membership in PTAS can be shown using a PTAS reduction, L-reduction, or P-reduction, all of which preserve PTAS membership, and these may also be used to demonstrate PTAS-completeness. On the other hand, showing non-membership in PTAS (namely, the nonexistence of a PTAS), may be done by showing that the problem is APX-hard, after which the existence of a PTAS would show P = NP. APX-hardness is commonly shown via PTAS reduction or AP-reduction.

== See also ==

* Parameterized approximation scheme, an approximation scheme that runs in FPT time

==References== <references/>

==External links== *Complexity Zoo: [https://complexityzoo.net/Complexity_Zoo:P#ptas PTAS], [https://complexityzoo.net/Complexity_Zoo:E#eptas EPTAS]. *Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, ''[https://www.csc.kth.se/tcs/compendium/ A compendium of NP optimization problems]'' – list which NP optimization problems have PTAS.

{{DEFAULTSORT:Polynomial-Time Approximation Scheme}} Category:Approximation algorithms Category:Complexity classes