Polynomial-time approximation scheme

In computer science, a polynomial-time approximation scheme (abbreviated 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 ε>0 and, in polynomial time, produces a solution that is within a factor ε of being optimal. For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most "(1+ε)L", with "L" being the length of the shortest tour. [Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753-782, 1998]

The running time of a PTAS is required to be polynomial in "n" for every fixed ε but can be different for different ε. Thus, an algorithm, running in time "O(n^1/ε)" or even "O(n^exp(1/ε))" counts as a PTAS.

Variants

A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O("n"^(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 "O(n^c)" for a constant "c" independent of ε. 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. 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 "n" and 1/ε. All problems in FPTAS are fixed-parameter tractable.

Unless P = NP, it holds that FPTAS $subsetneq$ PTAS $subsetneq$ APX. Consequently, under this assumption, APX-hard problems do not have PTASs.

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 ε>0 and, in polynomial time, produces a solution that has a "high probability" of being within a factor ε 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. Like a PTAS, a PRAS must have running time polynomial in "n", but not necessarily in ε; with further restrictions on the running time in ε, 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. [cite book
last = Vazirani
first = Vijay V.
title = Approximation Algorithms
publisher = Springer
date = 2003
pages = 294-5
location = Berlin
isbn = 3540653678]

An important class of problems which have an FPRAS, but were thought until recently not to have a PTAS, is the class of Sharp-P-complete counting problems. [Halman, Klabjan, Li, Orlin, Simchi-Levi, Fully polynomial time approximation schemes for stochastic dynamic programs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, 700-709, 2008]

References

External links

*Complexity Zoo: [http://qwiki.caltech.edu/wiki/Complexity_Zoo#ptas PTAS] , [http://qwiki.caltech.edu/wiki/Complexity_Zoo#eptas EPTAS] , [http://qwiki.caltech.edu/wiki/Complexity_Zoo#fptas FPTAS]
*Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ "A compendium of NP optimization problems"] - list which NP optimization problems have PTAS.