Polynomial-time approximation scheme

In computer science (particularly algorithmics), 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 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 the problem size 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. A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O(n^(1/ε)!). One way of addressing this is to define the efficient polynomial-time approximation scheme or EPTAS, in which the running time is required to be O(n^c) for a constant c 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 the big-O can still depend on ε arbitrarily. In other words, an EPTAS runs in FPT time where the parameter is ε. Even more restrictive, and useful in practice, is the fully polynomial-time approximation scheme or FPTAS, which requires the algorithm to be polynomial in both the problem size n and 1/ε. Unless P = NP, it holds that FPTAS ⊊ PTAS ⊊ APX. Consequently, under this assumption, APX-hard problems do not have PTASs. Another deterministic variant of the PTAS is the quasi-polynomial-time approximation scheme or QPTAS. A QPTAS has time complexity n^polylog(n) for each fixed ε > 0. Furthermore, a PTAS can run in FPT time for some parameterization of the problem, which leads to a parameterized approximation scheme.