Esquema de aproximación de tiempo polinómico

En informática, un esquema de aproximación de tiempo polinómico (PTAS) es un tipo de algoritmo de aproximación para problemas de optimización (la mayoría las veces, para problemas de optimización NP-difíciles).

Un PTAS es un algoritmo que toma un caso de un problema de optimización y un parámetro ε > 0, y produce una solución que se encuentra dentro de un factor 1 + ε de ser optimal (o 1 − ε para problemas de maximización). Por ejemplo, para el problema de viajante Euclidiano, un PTAS produciría una visita con longitud máximo (1 + ε)L, siendo L la longitud de la visita más corta.^[1]

El tiempo que toma en correr un PTAS es requerido ser polinomial en la longitud del problema para cada ε fijo, pero puede ser diferente para distintos valores de ε. Por esto, un algoritmo que corre en tiempo O(n^1/ε) o incluso O(n^exp(1/ε)) cuenta como 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 ε tiende a cero, por ejemplo, si el tiempo de ejecución es ${\displaystyle O(n^{(1/\varepsilon )!})}$. Una forma de abordar esto es definir el esquema de aproximación de tiempo polinomial eficiente o EPTAS, en el que se requiere que el tiempo de ejecución sea ${\displaystyle O(n^{c})}$ para una constante ${\displaystyle c}$ independiente de ${\displaystyle \varepsilon }$ . 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é ${\displaystyle \varepsilon }$ se esté usando; sin embargo, la constante bajo la notación O aún puede depender de ${\displaystyle \varepsilon }$ arbitrariamente. En otras palabras, un EPTAS se ejecuta en tiempo FPT donde el parámetro es ${\displaystyle \varepsilon }$.

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 ${\displaystyle n}$ como en ${\displaystyle 1/\varepsilon }$ .

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 cuasi-polinomial o QPTAS . Un QPTAS tiene una complejidad de tiempo ${\displaystyle n^{polylog(n)}}$ para cada ${\displaystyle \varepsilon >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 polinómica en tiempo 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 ε del óptimo. Convencionalmente, "alta probabilidad" significa una probabilidad superior a 3/4, aunque, como ocurre con la mayoría de las clases de complejidad probabilística, la definición es resistente a las variaciones de este valor exacto (el requisito mínimo es generalmente superior a 1/2). Al igual que un PTAS, un PRAS debe tener un polinomio de tiempo de ejecución 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 polinómico eficiente o EPRAS similar al EPTAS, y un esquema de aproximación aleatoria de tiempo polinomial completo o FPRAS similar al FPTAS.^[3]

Como 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, todas las cuales conservan la pertenencia al PTAS, y también se pueden usar para demostrar la completitud en PTAS. Por otro lado, mostrar la no pertenencia a PTAS (es decir, la inexistencia de un PTAS), se puede hacer mostrando que el problema es APX-difícil, después de lo cual la existencia de un PTAS mostraría P = NP. La dificultad APX se muestra comúnmente a través de la reducción PTAS o la reducción AP .

Véase también

• Esquema de aproximación parametrizada, un esquema de aproximación que se ejecuta en tiempo FPT

Referencias

1. Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
2. Jansen, Thomas (1998), «Introduction to the Theory of Complexity and Approximation Algorithms», en Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, eds., Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5-28, ISBN 9783540642015, doi:10.1007/BFb0053011.. See discussion following Definition 1.30 on p. 20.
3. Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294-295. ISBN 3-540-65367-8.

Enlaces externos

• Zoo de la Complejidad: PTAS, EPTAS .
• 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.