En la teoría de la computabilidad y la teoría de la complejidad computacional , especialmente en el estudio de algoritmos de aproximación , una reducción que preserva la aproximación es un algoritmo para transformar un problema de optimización en otro problema, de manera que la distancia entre las soluciones y el óptimo se conserva en cierto grado. Las reducciones que preservan la aproximación son un subconjunto de reducciones más generales en la teoría de la complejidad; la diferencia es que las reducciones que preservan la aproximación usualmente hacen declaraciones sobre problemas de aproximación o problemas de optimización , en contraposición a problemas de decisión .
Intuitivamente, el problema A se puede reducir al problema B mediante una reducción que conserva la aproximación si, dada una instancia del problema A y un solucionador (posiblemente aproximado) del problema B, se puede convertir la instancia del problema A en una instancia del problema B, aplicar el solucionador del problema B, y recuperar una solución para el problema A que también tiene alguna garantía de aproximación.
Definición
A diferencia de las reducciones en los problemas de decisión, una reducción que preserva la aproximación debe preservar más que la verdad de las instancias del problema cuando se reduce de un problema a otro. También debe mantener alguna garantía sobre la relación entre el costo de la solución y el costo del óptimo en ambos problemas. Para formalizar:
Dejar y Ser problemas de optimización.
Dejar ser una instancia de problema , con solución óptima . Dejar denotar el costo de una solución a una instancia de problema . Esta es también la métrica utilizada para determinar qué solución se considera óptima.
Una reducción que conserva la aproximación es un par de funciones (que a menudo debe ser computable en tiempo polinomial), de modo que:
- mapea una instancia de a una instancia de .
- mapea una solución de a una solución de .
- conserva alguna garantía del rendimiento de la solución , o relación de aproximación , definida como.
Tipos
Hay muchos tipos diferentes de reducciones de preservación de aproximación, todos los cuales tienen una garantía diferente (el tercer punto en la definición anterior). Sin embargo, a diferencia de otras reducciones, las reducciones que preservan la aproximación a menudo se superponen en las propiedades que demuestran en los problemas de optimización (por ejemplo, pertenencia a la clase de complejidad o integridad o inaproximación). Los diferentes tipos de reducciones se utilizan en cambio como técnicas de reducción variable, en el sentido de que se utiliza la reducción aplicable que se adapta más fácilmente al problema.
No todos los tipos de reducciones que preservan la aproximación pueden usarse para mostrar la pertenencia a todas las clases de complejidad de aproximación, las más notables de las cuales son PTAS y APX . Una reducción por debajo conserva la pertenencia a una clase de complejidad C si, dado un problema A que se reduce al problema B a través del esquema de reducción, y B está en C, entonces A también está en C. Algunas reducciones que se muestran a continuación solo preservan la membresía en APX o PTAS, pero no en el otro. Debido a esto, se debe hacer una elección cuidadosa al seleccionar una aproximación que preserva las reducciones, especialmente con el propósito de demostrar la completitud de un problema dentro de una clase de complejidad.
Crescenzi sugiere que los tres estilos de reducción más ideales, tanto por su facilidad de uso como por su potencia de prueba, son la reducción de PTAS, la reducción de AP y la reducción de L. [1] Las descripciones de reducción que siguen son de la encuesta de Crescenzi sobre reducciones que preservan la aproximación.
Reducción estricta
La reducción estricta es el tipo más simple de reducción de preservación de aproximación. En una reducción estricta, la razón de aproximación de una solución y 'a una instancia x' de un problema B debe ser como mucho tan buena como la razón de aproximación de la solución correspondiente y a la instancia x del problema A. En otras palabras:
- por .
La reducción estricta es la más sencilla: si existe una reducción estricta del problema A al problema B, entonces el problema A siempre se puede aproximar a una relación al menos tan buena como el problema B. La reducción estricta preserva la pertenencia tanto a PTAS como a APX.
Existe un concepto similar de reducción S, para el cual, y los óptimos de las dos instancias correspondientes también deben tener el mismo costo. La reducción S es un caso muy especial de reducción estricta y es aún más restrictivo. En efecto, los dos problemas A y B deben tener una correspondencia casi perfecta entre sí. La existencia de una reducción S implica no solo la existencia de una reducción estricta, sino todas las demás reducciones enumeradas aquí.
L-reducción
Las reducciones L preservan la membresía tanto en PTAS como en APX (pero solo para problemas de minimización en el caso de este último ). Como resultado, no se pueden utilizar en general para demostrar la integridad de los resultados de APX, Log-APX o Poly-APX, pero, sin embargo, se valoran por su formulación natural y facilidad de uso en las pruebas. [1]
Reducción de PTAS
La reducción de PTAS es otro esquema de reducción de uso común. Aunque conserva la membresía en PTAS, no lo hace para APX. No obstante, la completitud de APX se define en términos de reducciones de PTAS.
Las reducciones de PTAS son una generalización de las reducciones de P, que se muestran a continuación, con la única diferencia de que la función se permite depender de la relación de aproximación .
Reducción A y Reducción P
La reducción A y la reducción P son esquemas de reducción similares que se pueden usar para mostrar la membresía en APX y PTAS, respectivamente. Ambos introducen una nueva función, definido en números mayores que 1, que deben ser computables.
En una reducción A, tenemos que
- .
En una reducción P, tenemos que
- .
La existencia de una reducción P implica la existencia de una reducción PTAS.
E-reducción
La reducción E, que es una generalización de la reducción estricta pero implica tanto la reducción A como la reducción P, es un ejemplo de un estilo de reducción menos restrictivo que conserva la pertenencia no solo a PTAS y APX, sino también a las clases más grandes Log-APX y Poly-APX . E-reducción introduce dos nuevos parámetros, un polinomio y una constante . Su definición es la siguiente.
En una E-reducción, tenemos que para algún polinomio y constante ,
- , dónde denota el tamaño de la descripción de la instancia del problema.
- Para cualquier solucion a , tenemos .
Para obtener una reducción A de una reducción E, deje , y para obtener una reducción P a partir de una reducción E, sea .
Reducción de AP
Las reducciones de AP se utilizan para definir la integridad en las clases Log-APX y Poly-APX . Son un caso especial de reducción de PTAS, que cumple con las siguientes restricciones.
En una reducción de AP, tenemos eso para algunas constantes ,
con la generalización adicional de que la función se permite depender de la relación de aproximación , como en PTAS-reducción.
La reducción de AP es también una generalización de la reducción de E. En realidad, es necesario imponer una restricción adicional para la reducción de AP para preservar la membresía de Log-APX y Poly-APX, como lo hace la reducción de E: para un tamaño de problema fijo, el tiempo de cálculo de no debe aumentar a medida que aumenta la relación de aproximación.
Reducción de brechas
Una reducción de la brecha es un tipo de reducción que, si bien es útil para probar algunos resultados de inapropiabilidad, no se parece a las otras reducciones que se muestran aquí. Las reducciones de brechas tratan con problemas de optimización dentro de un contenedor de problemas de decisión, generados al cambiar el objetivo del problema para distinguir entre la solución óptima y las soluciones de algún factor multiplicativo peor que el óptimo.
Ver también
Referencias
- ↑ a b 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–. doi : 10.1109 / CCC.1997.612321 . ISBN 0-8186-7907-7.