In computer science, 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 ε > 0 and, in polynomial time, produces a solution that is within a factor 1 + ε of being optimal (or 1 - ε for maximization problems). 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.
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(n1/ε) or even O(nexp(1/ε)) counts as a PTAS.
Famous quotes containing the word scheme:
“Television programming for children need not be saccharine or insipid in order to give to violence its proper balance in the scheme of things.... But as an endless diet for the sake of excitement and sensation in stories whose plots are vehicles for killing and torture and little more, it is not healthy for young children. Unfamiliar as yet with the full story of human response, they are being misled when they are offered perversion before they have fully learned what is sound.”
—Dorothy H. Cohen (20th century)