Incomputer science (particularlyalgorithmics), apolynomial-time approximation scheme (PTAS) is a type ofapproximation algorithm foroptimization 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 produces a solution that is within a factor1 + ε of being optimal (or1 – ε for maximization problems). For example, for the Euclideantraveling salesman problem, a PTAS would produce a tour with length at most(1 + ε)L, withL being the length of the shortest tour.[1]
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 timeO(n1/ε) or evenO(nexp(1/ε)) counts as a PTAS.
A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime isO(n(1/ε)!). One way of addressing this is to define theefficient polynomial-time approximation scheme orEPTAS, in which the running time is required to beO(nc) for a constantc independent ofε. This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε is being used; however, the constant under thebig-O can still depend on ε arbitrarily. In other words, an EPTAS runs inFPT time where the parameter is ε.
Even more restrictive, and useful in practice, is thefully polynomial-time approximation scheme orFPTAS, which requires the algorithm to be polynomial in both the problem sizen and1/ε.
UnlessP = NP, it holds thatFPTAS ⊊ PTAS ⊊APX.[2] Consequently, under this assumption,APX-hard problems do not have PTASs.
Another deterministic variant of the PTAS is thequasi-polynomial-time approximation scheme orQPTAS. A QPTAS hastime complexitynpolylog(n) for each fixedε > 0. Furthermore, a PTAS can run inFPT time for some parameterization of the problem, which leads to aparameterized approximation scheme.
Some problems which do not have a PTAS may admit arandomized algorithm with similar properties, apolynomial-time randomized approximation scheme orPRAS. A PRAS is an algorithm which takes an instance of an optimization or counting problem and a parameterε > 0 and, in polynomial time, produces a solution that has ahigh probability of being within a factorε of optimal. Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement is generally greater than 1/2). Like a PTAS, a PRAS must have running time polynomial inn, but not necessarily inε; with further restrictions on the running time inε, one can define anefficient polynomial-time randomized approximation scheme orEPRAS similar to the EPTAS, and afully polynomial-time randomized approximation scheme orFPRAS similar to the FPTAS.[3]
The term PTAS may also be used to refer to the class of optimization problems that have a PTAS. PTAS is a subset ofAPX, and unlessP = NP, it is a strict subset.[2]
Membership in PTAS can be shown using aPTAS reduction,L-reduction, orP-reduction, all of which preserve PTAS membership, and these may also be used to demonstrate PTAS-completeness. On the other hand, showing non-membership in PTAS (namely, the nonexistence of a PTAS), may be done by showing that the problem is APX-hard, after which the existence of a PTAS would show P = NP. APX-hardness is commonly shown via PTAS reduction orAP-reduction.