Polynomial-time Approximation Scheme

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.

Other articles related to "approximation scheme":

Polynomial-time Approximation Scheme - Variants - Randomized
... 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 (1817–1862)