Editing Polynomial-time approximation scheme (section)

{{short description|Type of approximation algorithm}}

In [[computer science]] (particularly [[algorithmics]]), a '''polynomial-time approximation scheme''' ('''PTAS''') is a type of [[approximation algorithm]] for [[optimization problem]]s (most often, [[NP-hard]] optimization problems).

A PTAS is an algorithm which takes an instance of an optimization problem and a parameter {{math|ε > 0}} and produces a solution that is within a factor {{math|1 + ε}} of being optimal (or {{math|1 – ε}} for maximization problems). For example, for the Euclidean [[traveling salesman problem]], a PTAS would produce a tour with length at most {{math|(1 + ε)''L''}}, with {{mvar|L}} being the length of the shortest tour.<ref>[[Sanjeev Arora]], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref> 

The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time {{math|''[[Big O notation|O]]''(''n''{{sup|1/ε}})}} or even {{math|''O''(''n''{{sup|exp(1/ε)}})}} counts as a PTAS.