Editing Polynomial-time approximation scheme (section)

===Deterministic===
A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is {{math|''O''(''n''{{sup|(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 {{math|''O''(''n''{{sup|''c''}})}} for a constant {{mvar|c}} independent of {{math|ε}}. 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 notation|big-O]] can still depend on ε arbitrarily. In other words, an EPTAS runs in [[Fixed-parameter algorithm|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 {{mvar|n}} and {{math|1/ε}}. 

Unless [[P = NP problem|P = NP]], it holds that {{nowrap|FPTAS ⊊ PTAS ⊊ [[APX]]}}.<ref name=Jansen>{{citation|first=Thomas|last=Jansen|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|pages=5–28|title=Lectures on Proof Verification and Approximation Algorithms|series=Lecture Notes in Computer Science |editor1-first=Ernst W.|editor1-last=Mayr|editor2-first=Hans Jürgen|editor2-last=Prömel|editor3-first=Angelika|editor3-last=Steger|editor3-link=Angelika Steger|publisher=Springer|year=1998|volume=1367 |isbn=9783540642015|doi=10.1007/BFb0053011}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p. 20].</ref> 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]] {{math|''n''{{sup|[[Polylogarithmic function|polylog]](''n'')}}}} for each fixed {{math|ε > 0}}. Furthermore, a PTAS can run in [[Fixed-parameter algorithm|FPT]] time for some parameterization of the problem, which leads to a [[Parameterized approximation algorithm|parameterized approximation scheme]].