Fully polynomial-time approximation scheme
A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value. The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.
- Comment
- enA fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value. The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.
- Has abstract
- enA fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least times the correct value, and at most times the correct value. In the context of optimization problems, the correct value is understood to be the value of the optimal solution, and it is often implied that an FPTAS should produce a valid solution (and not just the value of the solution). Returning a value and finding a solution with that value are equivalent assuming that the problem possesses self reducibility. Importantly, the run-time of an FPTAS is polynomial in the problem size and in 1/ε. This is in contrast to a general polynomial-time approximation scheme (PTAS). The run-time of a general PTAS is polynomial in the problem size for each specific ε, but might be exponential in 1/ε. The term FPTAS may also be used to refer to the class of problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.
- Is primary topic of
- Fully polynomial-time approximation scheme
- Label
- enFully polynomial-time approximation scheme
- Link from a Wikipage to an external page
- complexityzoo.net/Complexity_Zoo:F%23fptas
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Approximation algorithms
- Category:Complexity classes
- Dynamic programming
- Edge cover
- Fixed-parameter tractable
- Function problem
- Gerhard J. Woeginger
- Identical-machines scheduling
- Knapsack problem
- List of knapsack problems
- Multiple subset sum
- Multiway number partitioning
- Natural logarithm
- Optimization problem
- P = NP problem
- Partial Order
- Polynomial-time approximation scheme
- Pseudo-polynomial time
- Self reducibility
- Shortest path problem
- Strongly NP-complete
- Subset sum problem
- Total preorder
- Uniform-machines scheduling
- Unrelated-machines scheduling
- Location
- enLem.3.3
- SameAs
- GMP8Z
- Q110130630
- Subject
- Category:Approximation algorithms
- Category:Complexity classes
- WasDerivedFrom
- Fully polynomial-time approximation scheme?oldid=1122326805&ns=0
- WikiPageLength
- 34752
- Wikipage page ID
- 2047521
- Wikipage revision ID
- 1122326805
- WikiPageUsesTemplate
- Template:Reflist
- Template:Rp