HTML Microdata document

This HTML5 document contains 190 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/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbpedia-ko	http://ko.dbpedia.org/resource/
n22	https://complexityzoo.net/Complexity_Zoo:
n7	https://global.dbpedia.org/id/
dbpedia-he	http://he.dbpedia.org/resource/
yago	http://dbpedia.org/class/yago/
dbpedia-ru	http://ru.dbpedia.org/resource/
dbt	http://dbpedia.org/resource/Template:
dbpedia-uk	http://uk.dbpedia.org/resource/
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
dbpedia-pt	http://pt.dbpedia.org/resource/
dbpedia-pl	http://pl.dbpedia.org/resource/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
dbpedia-it	http://it.dbpedia.org/resource/
wikipedia-en	http://en.wikipedia.org/wiki/
dbpedia-fr	http://fr.dbpedia.org/resource/
dbpedia-zh	http://zh.dbpedia.org/resource/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
gold	http://purl.org/linguistics/gold/
dbr	http://dbpedia.org/resource/
dbpedia-ja	http://ja.dbpedia.org/resource/
n25	https://www.csc.kth.se/tcs/compendium/

Statements

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

Subject Item: dbr:List_of_University_of_California,_Berkeley_alumni
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

Subject Item: dbr:Approximation-preserving_reduction
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

Subject Item: dbr:Independent_set_(graph_theory)
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Intersection_number_(graph_theory)
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

Subject Item: dbr:♯P-complete
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:1-planar_graph
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

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

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

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

Subject Item: dbr:Epsilon-equilibrium
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

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

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

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

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

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

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

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

Subject Item: dbr:Halin's_grid_theorem
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Identical-machines_scheduling
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Joseph_S._B._Mitchell
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:PTAS
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageDisambiguates: dbr:Polynomial-time_approximation_scheme

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

Subject Item: dbr:Polynomial-time_randomized_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

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

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

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

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

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

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

Subject Item: dbr:Gadget_(computer_science)
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Gödel_Prize
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Job-shop_scheduling
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

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

Subject Item: dbr:Kemeny–Young_method
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:2-satisfiability
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Baker's_technique
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

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

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

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

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

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

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

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

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

Subject Item: dbr:Polynomial-time_approximation_scheme
rdf:type: yago:PsychologicalFeature100023100 yago:Activity100407535 yago:Procedure101023820 yago:Act100030358 yago:Event100029378 yago:Collection107951464 yago:WikicatComplexityClasses yago:Algorithm105847438 yago:WikicatApproximationAlgorithms yago:Abstraction100002137 dbo:Software yago:Group100031264 yago:Class107997703 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:label: Schema di approssimazione in tempo polinomiale 多项式时间近似算法 Wielomianowy schemat aproksymacji Polynomial-time approximation scheme 多項式時間近似スキーム Esquema de aproximação de tempo Polinomial Schéma d'approximation en temps polynomial Схема наближення до поліноміального часу Приближённая схема полиномиального времени 다항 시간 근사 해법
rdfs:comment: В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации. Wielomianowy schemat aproksymacji (ang. Polynomial-Time Approximation Scheme, w skrócie PTAS) – algorytm aproksymacyjny, który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego problemu optymalizacyjnego i którego złożoność czasowa jest wielomianowa dla każdej żądanej dokładności. En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS. 計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータを入力として受け取り、多項式時間内に最適解の倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さをとしたとき、高々の解を見つけることができる。 PTASの実行時間は、を固定すると、問題の大きさの多項式であることが求められるが、に対しては定められていない。このため、実行時間がやオーダーであっても、PTASである。 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다. PTAS는 어떤 주어진 상수 에 대해서, 최적해로부터 배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가 을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.) EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 에 독립적인 의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, 는 EPTAS이다. У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації. In computer science (particularly algorithmics), 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. In informatica, uno schema di approssimazione in tempo polinomiale (in inglese polynomial-time approximation scheme o PTAS) è un tipo di algoritmo di approssimazione per problemi di ottimizzazione (molto spesso, problemi di ottimizzazione NP-difficili). È richiesto che il tempo di esecuzione di un PTAS sia un tempo polinomiale in n per ogni ε fisso, ma può essere diverso per diversi ε. Così un algoritmo eseguito nel O(n1/ε) o anche in O(nexp(1/ε)) conta come un PTAS. 在计算机科学领域，（PTAS）是一种用于优化问题（最常见的是NP-hard优化问题）的近似算法。 PTAS使用一个大于0的参数 ε，产生一个对于最小化问题能在 1 + ε 倍最优解内的解决方案（或最大化问题的 1 − ε 倍）。例如，对于欧几里得旅行商问题，现有的最好PTAS 将产生一个长度最多为 (1 + ε) L 的解，其中L是最短行程的长度。 ε的大小越小，PTAS的近似性能比越靠近1，也即说明这个PTAS的计算结果越接近最优解。对于一个固定大小的ε，PTAS 的运行时间必须是（对于问题大小）多项式的（例如对于一个原时间复杂度为O(2^n)的算法，它的PTAS时间复杂度可以为O(n4*2k)，其中k为参数），但对于不同的 ε，可以是不同的。时间复杂度为O(n1/ε) 甚至O(nexp(1/ε)) 的算法同样属于 PTAS。 Em ciência da computação, um esquema de aproximação em tempo polinomial (PTAS) é um tipo de algoritmo de aproximação para problemas de otimização (na maioria das vezes, problemas de otimização NP-difíceis). Um PTAS é um algoritmo que toma como entrada uma instância de um problema de otimização e um parâmetro e, em tempo polinomial, produz uma solução que está dentro de um fator de ser ideal (ou para problemas de maximização). Por exemplo, para problema do caixeiro viajante Euclidiano, um PTAS iria produzir um percurso com duração no máximo , com sendo o comprimento do menor percurso .
dcterms:subject: dbc:Complexity_classes dbc:Approximation_algorithms
dbo:wikiPageID: 666431
dbo:wikiPageRevisionID: 1096385541
dbo:wikiPageWikiLink: dbr:L-reduction dbr:Fully_polynomial-time_approximation_scheme dbr:P_=_NP_problem dbr:Big_O_notation dbc:Complexity_classes dbr:Marek_Karpinski dbr:Polylog dbr:Gerhard_J._Woeginger dbr:Traveling_salesman_problem dbr:Randomized_algorithm dbc:Approximation_algorithms dbr:Optimization_problem dbr:Approximation-preserving_reduction dbr:Approximation_algorithm dbr:Computer_science dbr:NP-hard dbr:APX dbr:Algorithmics dbr:PTAS_reduction
dbo:wikiPageExternalLink: n22:P%23ptas n22:E%23eptas n25:
owl:sameAs: n7:4zoFC dbpedia-he:סכמת_קירוב_פולינומית wikidata:Q843550 dbpedia-zh:多项式时间近似算法 dbpedia-it:Schema_di_approssimazione_in_tempo_polinomiale dbpedia-uk:Схема_наближення_до_поліноміального_часу dbpedia-ru:Приближённая_схема_полиномиального_времени dbpedia-ja:多項式時間近似スキーム dbpedia-fr:Schéma_d'approximation_en_temps_polynomial dbpedia-pl:Wielomianowy_schemat_aproksymacji dbpedia-ko:다항_시간_근사_해법 yago-res:Polynomial-time_approximation_scheme freebase:m.0314dj dbpedia-pt:Esquema_de_aproximação_de_tempo_Polinomial
dbp:wikiPageUsesTemplate: dbt:Mvar dbt:Math dbt:Sup dbt:Clarify dbt:Short_description
dbo:abstract: 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다. PTAS는 어떤 주어진 상수 에 대해서, 최적해로부터 배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가 을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.) EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 에 독립적인 의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, 는 EPTAS이다. FPTAS(fully polynomial-time approximation scheme)는 EPTAS보다 더 강한 조건으로, PTAS 알고리즘 중에서 시간 복잡도가 에 대해서 다항 시간을 만족해야 한다. 예를 들어, 는 FPTAS를 만족하며, 는 PTAS이지만 FPTAS는 아니다. 計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータを入力として受け取り、多項式時間内に最適解の倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さをとしたとき、高々の解を見つけることができる。 PTASの実行時間は、を固定すると、問題の大きさの多項式であることが求められるが、に対しては定められていない。このため、実行時間がやオーダーであっても、PTASである。 En informatique, un schéma d'approximation en temps polynomial (en anglais polynomial-time approximation scheme, abrégé en PTAS) est une famille d'algorithmes d'approximation pour des problèmes d'optimisation combinatoire. On dit aussi plus simplement schéma d'approximation polynomial. Le plus souvent, les problèmes d'optimisation combinatoire considérés sont NP-difficiles. Plusieurs variantes des PTAS existent : des définitions plus restrictives comme les EPTAS et FPTAS, ou d'autres qui reposent sur les algorithmes probabilistes comme les PRAS et FPRAS. In computer science (particularly algorithmics), 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. В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации. У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації. Em ciência da computação, um esquema de aproximação em tempo polinomial (PTAS) é um tipo de algoritmo de aproximação para problemas de otimização (na maioria das vezes, problemas de otimização NP-difíceis). Um PTAS é um algoritmo que toma como entrada uma instância de um problema de otimização e um parâmetro e, em tempo polinomial, produz uma solução que está dentro de um fator de ser ideal (ou para problemas de maximização). Por exemplo, para problema do caixeiro viajante Euclidiano, um PTAS iria produzir um percurso com duração no máximo , com sendo o comprimento do menor percurso . O tempo de execução de um PTAS é necessariamente polinomial em n para cada ε fixado, mas pode ser diferente para diferentes ε. Assim, um algoritmo sendo executado em tempo , ou mesmo conta como um PTAS. In informatica, uno schema di approssimazione in tempo polinomiale (in inglese polynomial-time approximation scheme o PTAS) è un tipo di algoritmo di approssimazione per problemi di ottimizzazione (molto spesso, problemi di ottimizzazione NP-difficili). Un PTAS è un algoritmo che prende un'istanza di un problema di ottimizzazione e un parametro ε > 0 e, in tempo polinomiale, produce una soluzione che è ottimale entro un fattore 1 + ε (o 1 - ε per i problemi di massimizzazione). Ad esempio, per il problema euclideo del commesso viaggiatore, un PTAS produrrebbe un giro di lunghezza al massimo (1 + ε)L, con L che è la lunghezza del giro più breve. È richiesto che il tempo di esecuzione di un PTAS sia un tempo polinomiale in n per ogni ε fisso, ma può essere diverso per diversi ε. Così un algoritmo eseguito nel O(n1/ε) o anche in O(nexp(1/ε)) conta come un PTAS. 在计算机科学领域，（PTAS）是一种用于优化问题（最常见的是NP-hard优化问题）的近似算法。 PTAS使用一个大于0的参数 ε，产生一个对于最小化问题能在 1 + ε 倍最优解内的解决方案（或最大化问题的 1 − ε 倍）。例如，对于欧几里得旅行商问题，现有的最好PTAS 将产生一个长度最多为 (1 + ε) L 的解，其中L是最短行程的长度。 ε的大小越小，PTAS的近似性能比越靠近1，也即说明这个PTAS的计算结果越接近最优解。对于一个固定大小的ε，PTAS 的运行时间必须是（对于问题大小）多项式的（例如对于一个原时间复杂度为O(2^n)的算法，它的PTAS时间复杂度可以为O(n4*2k)，其中k为参数），但对于不同的 ε，可以是不同的。时间复杂度为O(n1/ε) 甚至O(nexp(1/ε)) 的算法同样属于 PTAS。 Wielomianowy schemat aproksymacji (ang. Polynomial-Time Approximation Scheme, w skrócie PTAS) – algorytm aproksymacyjny, który pozwala na uzyskanie dowolnie dobrego rozwiązania przybliżonego danego problemu optymalizacyjnego i którego złożoność czasowa jest wielomianowa dla każdej żądanej dokładności.
gold:hypernym: dbr:Algorithm
prov:wasDerivedFrom: wikipedia-en:Polynomial-time_approximation_scheme?oldid=1096385541&ns=0
dbo:wikiPageLength: 6099
foaf:isPrimaryTopicOf: wikipedia-en:Polynomial-time_approximation_scheme

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

Subject Item: dbr:FPRAS
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

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

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

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

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

Subject Item: dbr:NP-hardness
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

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

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

Subject Item: dbr:Unrelated-machines_scheduling
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Uniform-machines_scheduling
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme

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

Subject Item: dbr:Efficient_polynomial-time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Efficient_polynomial-time_randomized_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Efficient_polynomial_time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Polynomial_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:Polynomial_time_approximation_scheme
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:EPRAS
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

Subject Item: dbr:EPTAS
dbo:wikiPageWikiLink: dbr:Polynomial-time_approximation_scheme
dbo:wikiPageRedirects: dbr:Polynomial-time_approximation_scheme

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