Esquema de tiempo polinomial aproximado

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de abril de 2022; las comprobaciones requieren 2 ediciones .

En matemáticas , el esquema de aproximación de tiempo polinomial o el esquema de aproximación de tiempo polinomial ( PTAS ) denota una clase de algoritmos de tiempo polinomial aproximados para resolver problemas de optimización generalmente NP-difíciles . Si P = NP, entonces la introducción de este concepto pierde sentido. Por lo tanto, supondremos además que Р no coincide con NP. Y sin pérdida de generalidad, definimos el concepto para el problema de minimización.

Definición

PTAS es una familia de algoritmos dependientes del parámetro ε , tal que para un conjunto arbitrario de datos de algún problema de optimización y parámetro ε > 0, el algoritmo de la familia encuentra una solución en tiempo polinomial con la función objetivo S < (1 + ε)OPT, donde OPT es el mínimo de la función objetivo. Por ejemplo, para el problema del viajante de comercio en el espacio euclidiano, hay un PTAS que encuentra un camino transversal de longitud como máximo (1 + ε) L , donde L es la longitud del camino más corto. [una]

El tiempo de ejecución de PTAS debe depender polinómicamente de n para cualquier ε fijo, pero puede variar arbitrariamente a medida que ε cambia. Los algoritmos con tiempo de ejecución O ( n 1/ε ) o incluso O ( n exp(1/ε) ) son algoritmos PTAS.

Algoritmos deterministas

En los algoritmos PTAS, el exponente en la estimación de la complejidad puede crecer catastróficamente a medida que ε disminuye, por ejemplo, cuando el tiempo de ejecución es O( n (1/ε)! ), lo que hace que esta clase de algoritmos sea de poco interés desde un punto de vista práctico . . Se puede definir un esquema de aproximación de tiempo polinomial eficiente o un esquema de aproximación de tiempo polinomial eficiente ( EPTAS ) para el cual el tiempo de ejecución debe ser O ( n c ), donde la constante c es independiente de ε. Esto asegura que al aumentar el tamaño de los datos de entrada aumenta el tiempo de ejecución, independientemente del valor de ε; sin embargo, el factor bajo el signo O sigue dependiendo arbitrariamente de ε. Otra restricción más útil en la práctica es el esquema de aproximación de tiempo totalmente polinomial ( FPTAS ), que requiere que el tiempo de ejecución del algoritmo dependa polinómicamente del tamaño del problema n y 1/ε. Un ejemplo de un problema para el que existe FPTAS es el problema de la mochila . Pero ni siquiera existe un PTAS para el problema relacionado con la creación de contenedores .

Cualquier problema de optimización fuertemente NP-duro con una función objetivo acotada polinómicamente no puede tener un FPTAS. [2] Sin embargo, lo contrario no es cierto. El problema de la mochila 2D no es fuertemente NP-hard, pero no tiene FPTAS incluso cuando la función objetivo está acotada polinomialmente. [3]

Ejecute FPTAS ⊊ PTAS ⊊  APX . Por lo tanto, los problemas APX-hard no tienen PTAS.

Otra modificación de PTAS es el esquema de aproximación de tiempo cuasi-polinomio ( QPTAS ) . QPTAS tiene complejidad de tiempo para cualquier fijo .

Algoritmos aleatorios

Algunos problemas que no tienen PTAS pueden tener algoritmos aleatorios con propiedades similares: esquema de aproximación aleatoria de tiempo polinomial o esquema de aproximación aleatoria de tiempo polinomial ( PRAS ). El algoritmo PRAS con el parámetro ε > 0 para un conjunto de datos arbitrarios del problema de optimización encuentra en tiempo polinomial una solución que no excede (1 + ε)OPT con una alta probabilidad. Por lo general, "alta probabilidad" significa una probabilidad superior a 3/4, aunque la definición no especifica este valor. Al igual que el algoritmo PTAS, el algoritmo PRAS debe tener un tiempo de ejecución que dependa polinómicamente de n , pero no de 1/ε. Por analogía con los algoritmos deterministas, se introducen EPRAS similares a EPTAS y FPRAS similares a FPTAS. [2]

Notas

  1. ↑ Sanjeev Arora , Esquemas de aproximación de tiempo polinomial para TSP euclidiano y otros problemas geométricos, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 2 Vazirani, Vijay V. Algoritmos de aproximación  (indefinidos) . - Berlín: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer y U. Pferschy y D. Pisinger. Problemas de mochila  (neopr.) . — Springer, 2004.

Enlaces