Polynomial-time approximation scheme

From Wikipedia, the free encyclopedia

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 produces a solution of an optimization problem that is within ε factor of being optimal. For example, for traveling salesman problem, a PTAS would produce a tour with length at most (1+ε)L, with L being the length of the shortest tour.

For a given heuristic A and TSP instance I, let A(I) denote the length of the tour produced by A and let OPT (I) denote the length of an optimal tour. Assuming P is not NP, no polynomial-time TSP heuristic can guarantee A(I)/OPT (I) be less than 2^p(N) for any fixed polynomial p and all instances I. Fortunately, there do exist some heuristic algorithm A that not guarantee but always produce good result. Especially, when geometric rule or triangle inequality are applied on TSP, the resulted length is even shorter in a polynomial time.

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 PTAS.

The 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 was 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 PTAS APX. Consequently, under this assumption, APX-hard problems do not have PTASs.

The "TAS" in PTAS and its variants is pronounced "taz".

[edit] External links

• Complexity Zoo: PTAS, EPTAS, FPTAS
• 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.