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.[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 time O(n1/ε) or even O(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 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(nc) 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.[2] 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 complexitynpolylog(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.
Randomizededit
Some problems which do not have a PTAS may admit a randomized algorithm with similar properties, a polynomial-time randomized approximation scheme or PRAS. 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 a high 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 in n, but not necessarily in ε; with further restrictions on the running time in ε, one can define an efficient polynomial-time randomized approximation scheme or EPRAS similar to the EPTAS, and a fully polynomial-time randomized approximation scheme or FPRAS similar to the FPTAS.[3]
As a complexity classedit
The term PTAS may also be used to refer to the class of optimization problems that have a PTAS. PTAS is a subset of APX, and unless P = NP, it is a strict subset. [2]
Membership in PTAS can be shown using a PTAS reduction, L-reduction, or P-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 or AP-reduction.
^Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
^ abJansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN9783540642015. See discussion following Definition 1.30 on p. 20.
^Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN3-540-65367-8.
External linksedit
Complexity Zoo: PTAS, EPTAS.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems – list which NP optimization problems have PTAS.
November 01, 2023
polynomial, time, approximation, scheme, computer, science, particularly, algorithmics, polynomial, time, approximation, scheme, ptas, type, approximation, algorithm, optimization, problems, most, often, hard, optimization, problems, ptas, algorithm, which, ta. 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 e gt 0 and produces a solution that is within a factor 1 e of being optimal or 1 e for maximization problems For example for the Euclidean traveling salesman problem a PTAS would produce a tour with length at most 1 e L with L 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 e but can be different for different e Thus an algorithm running in time O n1 e or even O nexp 1 e counts as a PTAS Contents 1 Variants 1 1 Deterministic 1 2 Randomized 2 As a complexity class 3 See also 4 References 5 External linksVariants editDeterministic edit A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as e shrinks for example if the runtime is O n 1 e 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 nc for a constant c independent of e This ensures that an increase in problem size has the same relative effect on runtime regardless of what e is being used however the constant under the big O can still depend on e arbitrarily In other words an EPTAS runs in FPT time where the parameter is e 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 e Unless P NP it holds that FPTAS PTAS APX 2 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 npolylog n for each fixed e gt 0 Furthermore a PTAS can run in FPT time for some parameterization of the problem which leads to a parameterized approximation scheme Randomized edit Some problems which do not have a PTAS may admit a randomized algorithm with similar properties a polynomial time randomized approximation scheme or PRAS A PRAS is an algorithm which takes an instance of an optimization or counting problem and a parameter e gt 0 and in polynomial time produces a solution that has a high probability of being within a factor e 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 in n but not necessarily in e with further restrictions on the running time in e one can define an efficient polynomial time randomized approximation scheme or EPRAS similar to the EPTAS and a fully polynomial time randomized approximation scheme or FPRAS similar to the FPTAS 3 As a complexity class editThe term PTAS may also be used to refer to the class of optimization problems that have a PTAS PTAS is a subset of APX and unless P NP it is a strict subset 2 Membership in PTAS can be shown using a PTAS reduction L reduction or P 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 or AP reduction See also editParameterized approximation scheme an approximation scheme that runs in FPT timeReferences edit Sanjeev Arora Polynomial time Approximation Schemes for Euclidean TSP and other Geometric Problems Journal of the ACM 45 5 753 782 1998 a b Jansen Thomas 1998 Introduction to the Theory of Complexity and Approximation Algorithms in Mayr Ernst W Promel Hans Jurgen Steger Angelika eds Lectures on Proof Verification and Approximation Algorithms Springer pp 5 28 doi 10 1007 BFb0053011 ISBN 9783540642015 See discussion following Definition 1 30 on p 20 Vazirani Vijay V 2003 Approximation Algorithms Berlin Springer pp 294 295 ISBN 3 540 65367 8 External links editComplexity Zoo PTAS EPTAS Pierluigi Crescenzi Viggo Kann Magnus Halldorsson Marek Karpinski and Gerhard Woeginger A compendium of NP optimization problems list which NP optimization problems have PTAS Retrieved from https en wikipedia org w index php title Polynomial time approximation scheme amp oldid 1147800991, wikipedia, wiki, book, books, library,
