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.
Other articles related to "approximation scheme":
... algorithm with similar properties, a polynomial-time randomized approximation scheme or PRAS ... in ε with further restrictions on the running time in ε, one can define an efficient polynomial-time randomized approximation scheme or EPRAS similar ...
Famous quotes containing the word scheme:
“I have no scheme about it,no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (18171862)