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).
10-433: PTAS or Ptas may refer to: Polynomial-time approximation scheme , an approximation algorithm in computer science Pesetas , Spanish currency PTAS reduction , an approximation-preserving reduction in computational complexity theory Preferential trading area , another term for a trade bloc See also [ edit ] PTA (disambiguation) Topics referred to by
20-399: 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 ) or even O ( n ) counts as a PTAS. A practical problem with PTAS algorithms is that the exponent of
30-435: 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
40-579: 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
50-479: Is different from Wikidata All article disambiguation pages All disambiguation pages Polynomial-time approximation scheme 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 ,
60-532: 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. The term PTAS may also be used to refer to
70-500: The PTAS is the quasi-polynomial-time approximation scheme or QPTAS . A QPTAS has time complexity 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 . 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
80-399: The class of optimization problems that have a PTAS. PTAS is a subset of APX , and unless P = NP , it is a strict subset. 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
90-406: The polynomial could increase dramatically as ε shrinks, for example if the runtime is O ( n ) . 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 ) for a constant c independent of ε . This ensures that an increase in problem size has the same relative effect on runtime regardless of what ε
100-405: The same term [REDACTED] This disambiguation page lists articles associated with the title PTAS . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=PTAS&oldid=1176350944 " Category : Disambiguation pages Hidden categories: Short description
#150849