Reducción de PTAS

En la teoría de la complejidad computacional , una reducción PTAS es una reducción que preserva la aproximación y que se utiliza a menudo para realizar reducciones entre soluciones de problemas de optimización . Conserva la propiedad de que un problema tiene un esquema de aproximación de tiempo polinomial (PTAS) y se utiliza para definir la completitud de ciertas clases de problemas de optimización como APX . Notacionalmente, si hay una reducción PTAS de un problema A a un problema B, escribimos . ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$

Con reducciones de muchos-uno en tiempo polinomial ordinarias , si podemos describir una reducción de un problema A a un problema B, entonces cualquier solución en tiempo polinomial para B puede ser compuesta con esa reducción para obtener una solución en tiempo polinomial para el problema A. De manera similar, nuestro objetivo al definir reducciones PTAS es que, dada una reducción PTAS de un problema de optimización A a un problema B, una PTAS para B puede ser compuesta con la reducción para obtener una PTAS para el problema A. ^[1]

Definición

Formalmente, definimos una reducción PTAS de A a B utilizando tres funciones computables en tiempo polinomial, f , g y α , con las siguientes propiedades:

• f asigna instancias del problema A a instancias del problema B.
• g toma una instancia x del problema A, una solución aproximada al problema correspondiente en B y un parámetro de error ε y produce una solución aproximada a x . ${\displaystyle f(x)}$
• α asigna parámetros de error a soluciones de instancias del problema A a parámetros de error a soluciones del problema B.
• Si la solución y para (una instancia del problema B) es, en la mayoría de los casos, peor que la solución óptima, entonces la solución correspondiente a x (una instancia del problema A) es, en la mayoría de los casos, peor que la solución óptima. ${\displaystyle f(x)}$ ${\displaystyle 1+\alpha (\epsilon )}$ ${\displaystyle g(x,y,\epsilon )}$ ${\displaystyle 1+\epsilon }$

Propiedades

De la definición se desprende claramente que:

• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$y ${\displaystyle {\text{B}}\in {\text{PTAS}}\implies {\text{A}}\in {\text{PTAS}}}$
• ${\displaystyle {\text{A}}\leq _{\text{PTAS}}{\text{B}}}$y ${\displaystyle {\text{A}}\not \in {\text{PTAS}}\implies {\text{B}}\not \in {\text{PTAS}}}$

Las reducciones L implican reducciones PTAS. Como resultado, se puede demostrar la existencia de una reducción PTAS a través de una reducción L. ^[1]

Las reducciones PTAS se utilizan para definir la completitud en APX , la clase de problemas de optimización con algoritmos de aproximación de factores constantes.

Véase también

• Reducción que preserva la aproximación
• Reducción en L
• APX

Referencias

1. Crescenzi, Pierluigi (1997). "Una breve guía para las reducciones que preservan la aproximación". Actas de Computational Complexity. Duodécima Conferencia Anual del IEEE . Washington, DC: IEEE Computer Society. págs. 262–273. doi :10.1109/CCC.1997.612321. ISBN . 0-8186-7907-7. Número de identificación del sujeto  18911241.

• Ingo Wegener. Teoría de la complejidad: exploración de los límites de los algoritmos eficientes. ISBN 3-540-21045-8 . Capítulo 8, págs. 110-111. Vista previa de Google Books