About: Fully polynomial-time approximation scheme

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Fully polynomial-time approximation scheme Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximately-optimal solutions to optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a solution whose value is - * At least 1 − ε times the optimal solution - in case of a maximization problem, or - * At most 1 + ε times the optimal solution - in case of a minimization problem. The term FPTAS may also be used to refer to the class of optimization problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset.

Attributes	Values
rdfs:label	Fully polynomial-time approximation scheme (en)
rdfs:comment	A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximately-optimal solutions to optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a solution whose value is - * At least 1 − ε times the optimal solution - in case of a maximization problem, or - * At most 1 + ε times the optimal solution - in case of a minimization problem. The term FPTAS may also be used to refer to the class of optimization problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset. (en)
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Rp
Subject	Approximation algorithms Complexity classes
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Fully_polynomial-time_approximation_scheme?oldid=1069487886&ns=0
Wikipage page ID	2047521 (xsd:integer)
page length (characters) of wiki page	34448 (xsd:nonNegativeInteger)
Wikipage revision ID	1069487886 (xsd:integer)
Link from a Wikipage to another Wikipage	Uniform-machines scheduling Algorithm Unrelated-machines scheduling Approximation algorithms Complexity classes Gerhard J. Woeginger P versus NP problem Pseudo-polynomial time Dynamic programming Edge cover Optimization problem Parameterized complexity Partially ordered set Identical-machines scheduling Preference relation Strong NP-completeness Subset sum problem Knapsack problem List of knapsack problems Multiple subset sum Multiway number partitioning Natural logarithm Polynomial-time approximation scheme Shortest path problem
has abstract	A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximately-optimal solutions to optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a solution whose value is - * At least 1 − ε times the optimal solution - in case of a maximization problem, or - * At most 1 + ε times the optimal solution - in case of a minimization problem. 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 optimization problems that have an FPTAS. FPTAS is a subset of PTAS, and unless P = NP, it is a strict subset. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Fully_polynomial-time_approximation_scheme
is Wikipage redirect of	FPTAS Fptas Fully-polynomial time approximation scheme Fully polynomial approximation scheme Fully polynomial time approximation scheme
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Bin covering problem Combinatorial optimization Minimum-weight triangulation Envy minimization FPTAS Fptas Multi-commodity flow problem Fully-polynomial time approximation scheme Fully polynomial approximation scheme Fully polynomial time approximation scheme Knapsack problem
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Fully_polynomial-time_approximation_scheme

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software