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*(*n*1/ε) or even *O*(*n*exp(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)