Hispanopedia WikiEn informática (en particular en algoritmia ), un esquema de aproximación en tiempo polinomial ( PTAS ) es un tipo de algoritmo de aproximación para problemas de optimización (generalmente, problemas de optimización NP-difíciles ).
Un PTAS es un algoritmo que toma una instancia de un problema de optimización y un parámetro ε > 0 y produce una solución que está dentro de un factor de 1 + ε de ser óptima (o 1 – ε para problemas de maximización). Por ejemplo, para el problema del viajante de comercio euclidiano , un PTAS produciría un recorrido con una longitud como máximo de (1 + ε) L , donde L es la longitud del recorrido más corto. [ 1 ]
El tiempo de ejecución de un PTAS debe ser polinomial en el tamaño del problema para cada ε fijo, pero puede ser diferente para distintos ε. Por lo tanto, un algoritmo que se ejecuta en tiempo O ( n 1/ε ) o incluso O ( n exp(1/ε) ) se considera un PTAS.
Variantes
Determinista
Un problema práctico con los algoritmos PTAS es que el exponente del polinomio podría aumentar drásticamente a medida que ε disminuye, por ejemplo, si el tiempo de ejecución es O ( n (1/ε)! ) . Una forma de abordar esto es definir el esquema de aproximación eficiente en tiempo polinomial o EPTAS , en el que se requiere que el tiempo de ejecución sea O ( n c ) para una constante c independiente de ε . Esto garantiza que un aumento en el tamaño del problema tenga el mismo efecto relativo en el tiempo de ejecución independientemente de qué ε se esté utilizando; sin embargo, la constante bajo la notación Big-O aún puede depender de ε arbitrariamente. En otras palabras, un EPTAS se ejecuta en tiempo FPT donde el parámetro es ε.
Aún más restrictivo, y útil en la práctica, es el esquema de aproximación de tiempo totalmente polinomial o FPTAS , que requiere que el algoritmo sea polinomial tanto en el tamaño del problema n como en 1/ε .
A menos que P = NP , se cumple que FPTAS ⊊ PTAS ⊊ APX . [ 2 ] En consecuencia, bajo esta suposición, los problemas APX-difíciles no tienen PTAS.
Otra variante determinista del PTAS es el esquema de aproximación de tiempo cuasipolinomial o QPTAS . Un QPTAS tiene una complejidad temporal de n polilog ( n ) para cada ε > 0 fijo . Además, un PTAS puede ejecutarse en tiempo FPT para alguna parametrización del problema, lo que conduce a un esquema de aproximación parametrizado .
Aleatorizado
Algunos problemas que no tienen un PTAS pueden admitir un algoritmo aleatorio con propiedades similares, un esquema de aproximación aleatoria de tiempo polinomial o PRAS . Un PRAS es un algoritmo que toma una instancia de un problema de optimización o conteo y un parámetro ε > 0 y, en tiempo polinomial, produce una solución que tiene una alta probabilidad de estar dentro de un factor ε de la óptima. Convencionalmente, "alta probabilidad" significa una probabilidad mayor que 3/4, aunque, como ocurre con la mayoría de las clases de complejidad probabilística, la definición es robusta a variaciones en este valor exacto (el requisito mínimo es generalmente mayor que 1/2). Al igual que un PTAS, un PRAS debe tener un tiempo de ejecución polinomial en n , pero no necesariamente en ε ; con restricciones adicionales en el tiempo de ejecución en ε , se puede definir un esquema de aproximación aleatoria de tiempo polinomial eficiente o EPRAS similar al EPTAS, y un esquema de aproximación aleatoria de tiempo totalmente polinomial o FPRAS similar al FPTAS. [ 3 ]
Como una clase de complejidad
El término PTAS también puede usarse para referirse a la clase de problemas de optimización que tienen un PTAS. PTAS es un subconjunto de APX y, a menos que P = NP , es un subconjunto estricto. [ 2 ]
La pertenencia a PTAS se puede demostrar mediante una reducción de PTAS , una reducción L o una reducción P , las cuales preservan la pertenencia a PTAS, y también se pueden usar para demostrar la completitud de PTAS. Por otro lado, la no pertenencia a PTAS (es decir, la inexistencia de un PTAS) se puede demostrar mostrando que el problema es APX-difícil, tras lo cual la existencia de un PTAS demostraría P = NP. La dureza APX se suele demostrar mediante una reducción de PTAS o una reducción AP .
Véase también
- Esquema de aproximación parametrizado , un esquema de aproximación que se ejecuta en tiempo FPT.
Referencias
- ↑ Sanjeev Arora , Esquemas de aproximación en tiempo polinomial para el TSP euclidiano y otros problemas geométricos, Journal of the ACM 45(5) 753–782, 1998.
- 1 2 Jansen, Thomas (1998), "Introducción a la teoría de la complejidad y los algoritmos de aproximación", en Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms , Lecture Notes in Computer Science, vol. 1367, Springer, pp. 5–28 , doi : 10.1007/BFb0053011 , ISBN 9783540642015. Véase la discusión que sigue a la Definición 1.30 en la página 20 .
- ^ Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. págs. 294–295 . ISBN 3-540-65367-8.
Enlaces externos
- Complexity Zoo: PTAS , EPTAS .
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger , Un compendio de problemas de optimización NP : lista de los problemas de optimización NP que tienen PTAS.
- Algoritmos de aproximación
- Clases de complejidad