| dbo:abstract
|
- 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. (fr)
- 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. (en)
- 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. (it)
- 計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は 倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
- 다항 시간 근사 해법(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는 아니다. (ko)
- 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. (pl)
- 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. (pt)
- В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации. (ru)
- 在计算机科学领域，（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。 (zh)
- У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації. (uk)
|
| rdfs:comment
|
- 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. (fr)
- 計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は 倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
- 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. (pl)
- В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации. (ru)
- 在计算机科学领域，（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。 (zh)
- У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації. (uk)
- 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. (en)
- 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)은 최적화 문제에 대한 근사 알고리즘의 한 종류이다. 주로 NP-난해 문제에 적용된다. PTAS는 어떤 주어진 상수 에 대해서, 최적해로부터 배를 넘지 않는 해답을 찾아내는 알고리즘을 의미한다. 예를 들어, 유클리드 공간상의 외판원 문제에 대한 PTAS는 길이가 을 넘지 않는 순회 경로를 만들어낸다. 여기서 L은 가장 짧은 순회 경로의 길이이다. (참고로, 일반적인 외판원 문제에 대한 근사 알고리즘은 P=NP가 아닌 한 존재하지 않는다.) EPTAS(efficient polynomial-time approximation scheme)는 PTAS 알고리즘 중에서 시간 복잡도가 꼴인, 즉 시간 복잡도를 대문자 O 표기법으로 표시했을 때 에 독립적인 의 꼴로 표현될 수 있는 알고리즘을 의미한다. 예를 들어, 는 EPTAS이다. (ko)
- 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. (it)
- 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 . (pt)
|
