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.
- Comment
- enIn 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.
- Has abstract
- enIn 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(n1/ε) or even O(nexp(1/ε)) counts as a PTAS.
- Hypernym
- Algorithm
- Is primary topic of
- Polynomial-time approximation scheme
- Label
- enPolynomial-time approximation scheme
- Link from a Wikipage to an external page
- complexityzoo.net/Complexity_Zoo:E%23eptas
- complexityzoo.net/Complexity_Zoo:P%23ptas
- www.csc.kth.se/tcs/compendium/
- Link from a Wikipage to another Wikipage
- Algorithmics
- Approximation algorithm
- Approximation-preserving reduction
- APX
- Big O notation
- Category:Approximation algorithms
- Category:Complexity classes
- Computer science
- Fully polynomial-time approximation scheme
- Gerhard J. Woeginger
- L-reduction
- Marek Karpinski
- NP-hard
- Optimization problem
- P = NP problem
- Polylog
- PTAS reduction
- Randomized algorithm
- Traveling salesman problem
- SameAs
- 4zoFC
- Esquema de aproximação de tempo Polinomial
- m.0314dj
- Polynomial-time approximation scheme
- Q843550
- Schéma d'approximation en temps polynomial
- Schema di approssimazione in tempo polinomiale
- Wielomianowy schemat aproksymacji
- Приближённая схема полиномиального времени
- Схема наближення до поліноміального часу
- סכמת קירוב פולינומית
- 多項式時間近似スキーム
- 多项式时间近似算法
- 다항 시간 근사 해법
- Subject
- Category:Approximation algorithms
- Category:Complexity classes
- WasDerivedFrom
- Polynomial-time approximation scheme?oldid=1096385541&ns=0
- WikiPageLength
- 6099
- Wikipage page ID
- 666431
- Wikipage revision ID
- 1096385541
- WikiPageUsesTemplate
- Template:Clarify
- Template:Math
- Template:Mvar
- Template:Short description
- Template:Sup