De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En informática , un esquema de aproximación de tiempo polinomial ( PTAS ) es un tipo de algoritmo de aproximación para problemas de optimización (con mayor frecuencia, problemas de optimización NP-hard ).

Un PTAS es un algoritmo que toma una instancia de un problema de optimización y un parámetro ε> 0 y, en tiempo polinomial, produce una solución que está dentro de un factor 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 (1 + ε) L , siendo L la longitud del recorrido más corto. [1] También existen PTAS para la clase de todos los problemas de satisfacción de restricciones densas (CSP). [2] [ aclaración necesaria ]

Se requiere que el tiempo de ejecución de un PTAS sea polinomio en n para cada ε fijo, pero puede ser diferente para diferentes ε. Por lo tanto, un algoritmo que se ejecuta en el tiempo O ( n 1 / ε ) o incluso O ( n exp (1 / ε) ) cuenta como un PTAS.

Variantes [ editar ]

Determinista [ editar ]

Un problema práctico con los algoritmos PTAS es que el exponente del polinomio podría aumentar drásticamente a medida que ε se reduce, por ejemplo, si el tiempo de ejecución es O ( n (1 / ε)! ). Una forma de abordar esto es definir el esquema de aproximación de tiempo polinómico eficiente o EPTAS , en el que se requiere que el tiempo de ejecución sea O ( n c ) para una constante c independiente de ε. Esto asegura 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 el gran O todavía puede depender de ε arbitrariamente. Aún más restrictivo, y útil en la práctica, es elesquema de aproximación en tiempo polinomial completo o FPTAS , que requiere que el algoritmo sea polinomial tanto en el tamaño del problema n como en 1 / ε. Todos los problemas en FPTAS son tratables con parámetros fijos con respecto a la parametrización estándar. Por ejemplo, el problema de la mochila admite un FPTAS. [3]

Cualquier problema de optimización fuertemente NP-duro con una función objetivo acotada polinomialmente no puede tener un FPTAS a menos que P = NP. [4] Sin embargo, lo contrario falla: por ejemplo, si P no es igual a NP, la mochila con dos restricciones no es fuertemente NP-dura, pero no tiene FPTAS incluso cuando el objetivo óptimo está acotado polinomialmente. [5]

A menos que P = NP , se mantiene que FPTAS ⊊ PTAS ⊊  APX . [6] En consecuencia, bajo este supuesto, los problemas APX-hard no tienen PTAS.

Otra variante determinista del PTAS es el esquema de aproximación de tiempo cuasi-polinomial o QPTAS . Un QPTAS tiene una complejidad de tiempo para cada fijo .

Aleatorizado [ editar ]

Algunos problemas que no tienen un PTAS pueden admitir un algoritmo aleatorizado con propiedades similares, un esquema de aproximación aleatorizado 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 óptimo. Convencionalmente, "alta probabilidad" significa probabilidad mayor que 3/4, aunque como 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). Como un PTAS, un PRAS debe tener un polinomio de tiempo de ejecución en n, pero no necesariamente en ε; con más restricciones en el tiempo de ejecución en ε, se puede definir un esquema de aproximación aleatoria en tiempo polinómico eficiente o EPRAS similar al EPTAS, y un esquema de aproximación aleatorio en tiempo polinomial completo o FPRAS similar al FPTAS. [4]

Como clase de complejidad [ editar ]

El término PTAS también se puede utilizar 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. [6]

La membresía en PTAS se puede demostrar usando una reducción de PTAS , una reducción L o una reducción P , todas las cuales preservan la membresía de PTAS, y también se pueden usar para demostrar que PTAS está completo. Por otro lado, mostrar la no membresía en PTAS (es decir, la inexistencia de un PTAS), se puede hacer mostrando que el problema es APX-hard, después de lo cual la existencia de un PTAS mostraría P = NP. La dureza APX se muestra comúnmente mediante la reducción de PTAS o la reducción de AP .

Referencias [ editar ]

  1. ^ Sanjeev Arora , Esquemas de aproximación de tiempo polinómico para TSP euclidiana y otros problemas geométricos, Revista del ACM 45 (5) 753–782, 1998.
  2. ↑ Arora, S .; Karger, D .; Karpinski, M. (1999), "Esquemas de aproximación de tiempo polinomial para casos densos de problemas NP-difíciles", Journal of Computer and System Sciences , 58 (1): 193-210, doi : 10.1006 / jcss.1998.1605
  3. ^ Vazirani, Vijay (2001). Algoritmos de aproximación . Berlín: Springer. págs.  69 –70. ISBN 3540653678. OCLC  47097680 .
  4. ↑ a b Vazirani, Vijay V. (2003). Algoritmos de aproximación . Berlín: Springer. págs. 294–295. ISBN 3-540-65367-8.
  5. ^ H. Kellerer y U. Pferschy y D. Pisinger (2004). Problemas con la mochila . Saltador.CS1 maint: uses authors parameter (link)
  6. ^ a b Jansen, Thomas (1998), "Introducción a la teoría de la complejidad y algoritmos de aproximación", en Mayr, Ernst W .; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms , Springer, págs. 5–28, doi : 10.1007 / BFb0053011 , ISBN 9783540642015. Véase la discusión que sigue a la Definición 1.30 en la pág. 20 .

Enlaces externos [ editar ]

  • Complejo zoológico: PTAS , EPTAS , FPTAS
  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger , Un compendio de problemas de optimización de NP : enumere qué problemas de optimización de NP tienen PTAS.