| dbo:abstract |
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. 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. (en) |
| dbo:wikiPageExternalLink |
https://complexityzoo.net/Complexity_Zoo:F%23fptas |
| dbo:wikiPageID |
2047521 (xsd:integer) |
| dbo:wikiPageLength |
34752 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1122326805 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Algorithm dbr:List_of_knapsack_problems dbr:Pseudo-polynomial_time dbc:Approximation_algorithms dbr:Shortest_path_problem dbr:Strongly_NP-complete dbr:Function_problem dbr:Identical-machines_scheduling dbr:Total_preorder dbr:Dynamic_programming dbr:Gerhard_J._Woeginger dbc:Complexity_classes dbr:Fixed-parameter_tractable dbr:Edge_cover dbr:Polynomial-time_approximation_scheme dbr:Natural_logarithm dbr:Optimization_problem dbr:Knapsack_problem dbr:Subset_sum_problem dbr:Multiple_subset_sum dbr:Multiway_number_partitioning dbr:Unrelated-machines_scheduling dbr:Uniform-machines_scheduling dbr:P_=_NP_problem dbr:Partial_Order dbr:Self_reducibility |
| dbp:location |
Lem.3.3 (en) |
| dbp:wikiPageUsesTemplate |
dbt:Reflist dbt:Rp |
| dct:subject |
dbc:Approximation_algorithms dbc:Complexity_classes |
| rdfs:comment |
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. (en) |
| rdfs:label |
Fully polynomial-time approximation scheme (en) |
| owl:sameAs |
wikidata:Fully polynomial-time approximation scheme https://global.dbpedia.org/id/GMP8Z |
| prov:wasDerivedFrom |
wikipedia-en:Fully_polynomial-time_approximation_scheme?oldid=1122326805&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Fully_polynomial-time_approximation_scheme |
| is dbo:wikiPageRedirects of |
dbr:FPTAS dbr:Fptas dbr:Fully-polynomial_time_approximation_scheme dbr:Fully_polynomial_approximation_scheme dbr:Fully_polynomial_time_approximation_scheme |
| is dbo:wikiPageWikiLink of |
dbr:Strong_NP-completeness dbr:Bin_covering_problem dbr:Polynomial-time_approximation_scheme dbr:FPTAS dbr:Fptas dbr:Fully-polynomial_time_approximation_scheme dbr:Fully_polynomial_approximation_scheme dbr:Fully_polynomial_time_approximation_scheme |
| is foaf:primaryTopic of |
wikipedia-en:Fully_polynomial-time_approximation_scheme |