HTML Microdata document

This HTML5 document contains 56 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n9	https://complexityzoo.net/Complexity_Zoo:
n15	https://global.dbpedia.org/id/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
prov	http://www.w3.org/ns/prov#
dbc	http://dbpedia.org/resource/Category:
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/

Statements

Subject Item: dbr:Strong_NP-completeness
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Fully_polynomial-time_approximation_scheme
rdfs:label: Fully polynomial-time approximation scheme
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.
dcterms:subject: dbc:Approximation_algorithms dbc:Complexity_classes
dbo:wikiPageID: 2047521
dbo:wikiPageRevisionID: 1122326805
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme dbr:Self_reducibility dbr:Strongly_NP-complete dbr:Dynamic_programming dbr:Multiple_subset_sum dbr:List_of_knapsack_problems dbr:Algorithm dbr:Uniform-machines_scheduling dbr:Subset_sum_problem dbr:P_=_NP_problem dbr:Multiway_number_partitioning dbr:Function_problem dbr:Total_preorder dbr:Fixed-parameter_tractable dbr:Pseudo-polynomial_time dbr:Shortest_path_problem dbc:Complexity_classes dbr:Edge_cover dbr:Partial_Order dbr:Gerhard_J._Woeginger dbr:Knapsack_problem dbr:Natural_logarithm dbr:Optimization_problem dbc:Approximation_algorithms dbr:Unrelated-machines_scheduling dbr:Identical-machines_scheduling
dbo:wikiPageExternalLink: n9:F%23fptas
owl:sameAs: wikidata:Q110130630 n15:GMP8Z
dbp:wikiPageUsesTemplate: dbt:Reflist dbt:Rp
dbp:location: Lem.3.3
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.
prov:wasDerivedFrom: wikipedia-en:Fully_polynomial-time_approximation_scheme?oldid=1122326805&ns=0
dbo:wikiPageLength: 34752
foaf:isPrimaryTopicOf: wikipedia-en:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Bin_covering_problem
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:FPTAS
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Fptas
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Fully-polynomial_time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Fully_polynomial_approximation_scheme
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: dbr:Fully_polynomial_time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Fully_polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Fully_polynomial-time_approximation_scheme

Subject Item: wikipedia-en:Fully_polynomial-time_approximation_scheme
foaf:primaryTopic: dbr:Fully_polynomial-time_approximation_scheme