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 Template:Math and produces a solution that is within a factor Template:Math of being optimal (or Template:Math for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most Template:Math, with Template:Mvar 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 Template:Math or even Template:Math counts as a PTAS.
VariantsEdit
DeterministicEdit
A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is Template:Math. 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 Template:Math for a constant Template:Mvar independent of Template: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 Template:Mvar and Template:Math.
Unless P = NP, it holds that Template:Nowrap.<ref name=Jansen>Template:Citation. See discussion following Definition 1.30 on 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 Template:Math for each fixed Template:Math. Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme.
RandomizedEdit
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 Template:Math and, in polynomial time, produces a solution that has a high probability of being within a factor Template: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 Template:Mvar, but not necessarily in Template:Math; with further restrictions on the running time in Template: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">Template:Cite book</ref>
As a complexity classEdit
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 alsoEdit
- Parameterized approximation scheme, an approximation scheme that runs in FPT time
ReferencesEdit
<references/>
External linksEdit
- Complexity Zoo: PTAS, EPTAS.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems – list which NP optimization problems have PTAS.