Esquema de aproximación de tiempo polinomial

Es un hecho muy conocido que no existe una solución de tiempo polinomial conocida para problemas NP completos y estos problemas ocurren mucho en el mundo real (ver this , this y this por ejemplo). Así que debe haber una manera de manejarlos. Hemos visto algoritmos para estos problemas que son p aproximados (por ejemplo, 2 aproximados para Travelling Salesman ). ¿Podemos hacerlo mejor?

El esquema de aproximación de tiempo polinomial ( PTAS ) es un tipo de algoritmo aproximado que permite al usuario controlar la precisión, lo cual es una característica deseable. Estos algoritmos toman un parámetro adicional ε > 0 y proporcionan una solución que es (1 + ε) aproximada para la minimización y (1 – ε) para la maximización. Por ejemplo, considere un problema de minimización, si ε es 0,5, entonces la solución proporcionada por el algoritmo PTAS es 1,5 aproximada. El tiempo de ejecución de PTAS debe ser polinomial en términos de n, sin embargo, puede ser exponencial en términos de ε.

En los algoritmos PTAS, el exponente del polinomio puede aumentar drásticamente a medida que ε se reduce, por ejemplo, si el tiempo de ejecución es O(n ^(1/ε)! ), lo cual es un problema. Existe un esquema más estricto, el Esquema de aproximación de tiempo totalmente polinomial ( FPTAS ) . En FPTAS, el algoritmo necesita polinomio tanto en el tamaño del problema n como en 1/ε.

Ejemplo (problema de la mochila 0-1):
      Sabemos que la mochila 0-1 es NP Completa. Hay una solución pseudopolinomial basada en DP para esto. Pero si los valores de entrada son altos, entonces la solución se vuelve inviable y se necesita una solución aproximada. Una solución aproximada es usar el enfoque codicioso (calcule el valor por kg para todos los artículos y coloque el valor más alto por kg primero si es menor que W), pero el enfoque codicioso no es PTAS, por lo que no tenemos control sobre la precisión.

A continuación se muestra una solución FPTAS para el problema de la mochila 0-1:
Entrada:
W (Capacidad de la mochila)
val[0..n-1] (Valores de los artículos)
wt[0..n-1] (Pesos de los artículos)

1. Encuentre el elemento de valor máximo, es decir, encuentre el valor máximo en val[]. Sea este valor máximo maxVal.
2. Calcule el factor de ajuste k para todos los valores

         k  = (maxVal * ε) / n

3. Ajuste todos los valores, es decir, cree una nueva array val'[] que divida los valores entre k. Haga lo siguiente para cada valor val[i].

         val'[i] = floor(val[i] / k)

4. Ejecute la solución basada en DP para valores reducidos, es decir, val'[0..n-1] y todos los demás parámetros iguales.

La solución anterior funciona en tiempo polinomial en términos de n y ε. La solución proporcionada por este FPTAS es (1 – ε) aproximada. La idea es redondear algunos de los dígitos de valores menos significativos, luego estarán limitados por un polinomio y 1/ε.

Ejemplo:

val[] = {12, 16, 4, 8}
wt[]  = {3, 4, 5, 2}
W = 10
ε = 0.5
 
maxVal = 16 [maximum value in val[]]
Adjustment factor, k = (16 * 0.5)/4 = 2.0

Now we apply DP based solution on below modified 
instance of problem.

val'[] = {6, 8, 2, 4}  [ val'[i] = floor(val[i]/k) ]
wt[] = {3, 4, 5, 2}
W = 10

¿Cómo es la solución (1 – ε) * OPT?
Aquí OPT es el valor óptimo. Sea S el conjunto producido por el algoritmo FPTAS anterior y el valor total de S sea val(S). Necesitamos mostrar que

       val(S) >= (1 - ε)*OPT 

Sea O el conjunto producido por la solución óptima (la solución con valor total OPT), es decir, val(O) = OPT.

       val(O) - k*val'(O) <= n*k 
       [Because val'[i] = floor(val[i]/k) ] 

Después del paso de programación dinámica, obtenemos un conjunto que es óptimo para la instancia escalada
y, por lo tanto, debe ser al menos tan bueno como elegir el conjunto O con las ganancias más pequeñas. De ahí podemos concluir,

      val'(S) >= k . val'(O)
              >= val(O) - nk
              >= OPT - ε * maxVal
              >= OPT - ε * OPT [OPT >= maxVal]
              >= (1 - ε) * OPT 

Fuentes:
http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf
https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme

Este artículo es una contribución de Dheeraj Gupta. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.