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 produce una solución que está dentro de un factor 1 + ε de ser óptimo (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]
Se requiere que el tiempo de ejecución de un PTAS sea polinomial en el tamaño del problema 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.
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 el esquema de aproximación de tiempo completamente polinómico 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 mantiene que FPTAS ⊊ PTAS ⊊ APX . [2] En consecuencia, bajo este supuesto, los problemas APX-hard no tienen PTAS.