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

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

A related notion is fully polynomial time approximation scheme or FPTAS in which the running time is required to be O(n^c) for a constant c independent of ε. The constant under big-O can still depend on ε arbitrarily.

External link

• A compendium of NP optimization problems - list which NP optimization problems have PTAS