Un esquema de aproximación de tiempo polinomial completo (FPTAS) es un algoritmo para encontrar soluciones aproximadamente óptimas a los problemas de optimización . Un FPTAS toma como entrada una instancia del problema y un parámetro ε> 0. Devuelve como salida una solución cuyo valor es -
Es importante destacar que el tiempo de ejecución de un FPTAS es polinomial en el tamaño del problema y en 1 / ε. Esto contrasta con un esquema general de aproximación de tiempo polinomial (PTAS). El tiempo de ejecución de un PTAS general es polinomial en el tamaño del problema para cada ε específico, pero podría ser exponencial en 1 / ε. [1]
El término FPTAS también se puede utilizar para referirse a la clase de problemas de optimización que tienen un FPTAS. FPTAS es un subconjunto de PTAS y, a menos que P = NP , es un subconjunto estricto. [2]
Todos los problemas en FPTAS son tratables con parámetros fijos con respecto a la parametrización estándar. [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]
Woeginger [6] presentó un esquema general para convertir una determinada clase de programas dinámicos en un FPTAS.