About: Polynomial-time approximation scheme

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

About: Polynomial-time approximation scheme Goto Sponge NotDistinct Permalink

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

In computer science, 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.

Attributes	Values
rdf:type	software
rdfs:label	Polynomial-time approximation scheme (en)
rdfs:comment	In computer science, 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. (en)
sameAs	Polynomial-time approximation scheme Polynomial-time approximation scheme
dbp:wikiPageUsesTemplate	dbt:Clarify
Subject	Approximation algorithms Complexity classes
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme?oldid=1060108159&ns=0
Wikipage page ID	666431 (xsd:integer)
page length (characters) of wiki page	5942 (xsd:nonNegativeInteger)
Wikipage revision ID	1060108159 (xsd:integer)
has abstract	In computer science, 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme
is Wikipage redirect of	FPRAS EPRAS EPTAS Efficient polynomial-time approximation scheme Efficient polynomial-time randomized approximation scheme Efficient polynomial time approximation scheme Fully polynomial-time randomized approximation scheme Polynomial-time randomized approximation scheme Polynomial approximation scheme Polynomial time approximation scheme
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures NP-hardness 1-planar graph 2-satisfiability APX Apex graph Approximation-preserving reduction Approximation algorithm Art gallery problem Baker's technique Barrier resilience Berlekamp switching game Bidimensionality Bin covering problem Bin packing problem Bipartite realization problem Boolean satisfiability problem Boson sampling Bounded expansion Joseph S. B. Mitchell David Shmoys Digraph realization problem Dominating set Job-shop scheduling Chromatic polynomial Cubic graph Dense subgraph K-minimum spanning tree Kinodynamic planning Linear extension Clique cover Clique problem Combinatorial optimization Computing the permanent Connected dominating set Convex volume approximation Correlation clustering List of University of California, Berkeley alumni List of algorithm general topics List of complexity classes Minimum k-cut Minimum routing cost spanning tree Closest string Envy minimization Epsilon-equilibrium Fully polynomial-time approximation scheme Gadget (computer science) Graph coloring Graph realization problem Identical-machines scheduling Independent set (graph theory) Kemeny–Young method FPRAS Exact algorithm Feedback arc set Guillotine partition Gödel Prize Halin's grid theorem Map graph EPRAS EPTAS Efficient polynomial-time approximation scheme Efficient polynomial-time randomized approximation scheme Efficient polynomial time approximation scheme Fully polynomial-time randomized approximation scheme Knapsack problem List of knapsack problems Matroid oracle Matroid parity problem Maximin share Maximum disjoint set Maximum satisfiability problem Multiple subset sum Multiway number partitioning

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, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software