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:
“The real security of Christianity is to be found in its benevolent morality, in its exquisite adaptation to the human heart, in the facility with which its scheme accommodates itself to the capacity of every human intellect, in the consolation which it bears to the house of mourning, in the light with which it brightens the great mystery of the grave.”
—Thomas Babington Macaulay (18001859)