En la teoría de la complejidad computacional , una reducción de PTAS es una reducción de preservación de aproximación que se usa a menudo para realizar reducciones entre soluciones a 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 . Notablemente, si hay una reducción de PTAS de un problema A a un problema B, escribimos.
Con reducciones ordinarias de tiempo polinomial de muchos uno , si podemos describir una reducción de un problema A a un problema B, entonces cualquier solución de tiempo polinomial para B se puede componer con esa reducción para obtener una solución de tiempo polinomial para el problema A De manera similar, nuestro objetivo al definir las reducciones de PTAS es que dada una reducción de PTAS de un problema de optimización A a un problema B, se pueda componer un PTAS para B con la reducción para obtener un PTAS para el problema A.
Definición
Formalmente, definimos una reducción de PTAS de A a B usando tres funciones computables de tiempo polinómico, f , g y α , con las siguientes propiedades:
- f mapea instancias del problema A con instancias del problema B.
- g toma una instancia x del problema A, una solución aproximada al problema correspondienteen B, y un parámetro de error ε y produce una solución aproximada de x .
- α asigna parámetros de error para soluciones a casos del problema A a parámetros de error para soluciones al problema B.
- Si la solución y a (una instancia del problema B) es como mucho veces peor que la solución óptima, entonces la solución correspondiente a x (una instancia de problema A) es como máximo veces peor que la solución óptima.
Propiedades
A partir de la definición, es sencillo demostrar que:
- y
- y
Las reducciones L implican reducciones de PTAS. Como resultado, se puede mostrar la existencia de una reducción de PTAS a través de una reducción L en su lugar. [1]
Las reducciones de PTAS se utilizan para definir la completitud en APX , la clase de problemas de optimización con algoritmos de aproximación de factor constante.
Ver también
Referencias
- ^ Crescenzi, Pierluigi (1997). "Una breve guía para las reducciones de conservación de aproximación" . Actas de la 12ª Conferencia Anual IEEE sobre Complejidad Computacional . Washington, DC: IEEE Computer Society: 262–.
- 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