Reducción que preserva la aproximación

En la teoría de la computabilidad y la teoría de la complejidad computacional , especialmente en el estudio de los algoritmos de aproximación , una reducción que preserva la aproximación es un algoritmo para transformar un problema de optimización en otro, de manera que la distancia de las soluciones al óptimo se conserve hasta cierto punto. Las reducciones que preservan la aproximación son casos especiales de las reducciones generales en la teoría de la complejidad; la diferencia radica en que las reducciones que preservan la aproximación suelen hacer afirmaciones sobre problemas de aproximación o de optimización , en lugar de problemas de decisión .

Intuitivamente, el problema A se puede reducir al problema B mediante una reducción que preserva la aproximación si, dada una instancia del problema A y un solucionador (posiblemente aproximado) para el problema B, se puede convertir la instancia del problema A en una instancia del problema B, aplicar el solucionador para el problema B y recuperar una solución para el problema A que también tenga alguna garantía de aproximación.

Antecedentes sobre problemas de optimización

Primero recordamos algunos conceptos de problemas de optimización, ilustrados con el problema del viajante (TSP) . Una instancia es la entrada del problema, es decir, la información que necesitamos para calcular una solución. Una instancia para el TSP es un conjunto finito de ciudades y las distancias entre ellas. Una solución es un recorrido que visita todas las ciudades. En el caso del TSP, el costo de una solución es la longitud del recorrido. Escribimos $\mathrm {OPT_{TSP}} (x)$ ser el costo de una solución óptima, es decir, la longitud del recorrido más corto. Sean A y B problemas de optimización y c _A y c _B sus respectivas funciones de costo.

Definición

A diferencia de las reducciones en problemas de decisión, una reducción que preserva la aproximación debe preservar más que la verdad de las instancias del problema al reducir 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:

Sean $A$ y $B$ problemas de optimización.

Sea $x$ una instancia del problema $A$ , con solución óptima ${\text{OPT}}(x)$ . Dejar $c_{A}(x,y)$ denota el costo de una solución $y$ para una instancia $x$ del problema $A.$ Esta es también la métrica utilizada para determinar qué soluciones se consideran óptimas.

Una reducción que preserva la aproximación es un par de funciones $(f,g)$ (que a menudo debe ser computable en tiempo polinomial), de tal manera que:

$f$ asigna una instancia $x$ de $A$ a una instancia $x'$ de $B.$
$g$ mapea una solución $y'$ de $B$ a una solución $y$ de $A.$
$g$ conserva alguna garantía del rendimiento de la solución , o relación de aproximación , definida como $R_{A}(x,y)=\max \left({\frac {c_{A}(x,{\text{OPT}}(x))}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,{\text{OPT}}(x))}}\right)$ .

Tipos

Existen diversos tipos de reducciones que preservan la aproximación, cada una con una garantía diferente (el tercer punto de la definición anterior). Sin embargo, a diferencia de otras reducciones, las reducciones que preservan la aproximación suelen presentar propiedades similares en problemas de optimización (por ejemplo, pertenencia a clases de complejidad , completitud o inaproximabilidad). En cambio, los distintos tipos de reducciones se utilizan como técnicas de reducción variables, empleando la que mejor se adapta al problema.

No todos los tipos de reducciones que preservan la aproximación pueden usarse para demostrar la pertenencia a todas las clases de complejidad de aproximabilidad, siendo las más notables PTAS y APX . Una reducción que se muestra a continuación preserva la pertenencia a una clase de complejidad C si, dado un problema A que se reduce al problema B mediante el esquema de reducción, y B pertenece a C, entonces A también pertenece a C. Algunas reducciones que se muestran a continuación solo preservan la pertenencia a APX o PTAS, pero no a las demás. Por ello, es necesario elegir cuidadosamente las reducciones que preservan la aproximación, especialmente para 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 poder de demostración, son la reducción PTAS, la reducción AP y la reducción L. ^{[ 1 ]} Las descripciones de reducción que siguen provienen del estudio 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 que preserva la 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 máximo tan buena como la razón de aproximación de la solución y correspondiente a la instancia x del problema A. En otras palabras:

R_{A}(x,y)\leq R_{B}(x',y')

para

x'=f(x),y=g(y')

.

La reducción estricta es la más directa: si existe una reducción estricta del problema A al problema B, entonces el problema A siempre se puede aproximar con una razón al menos tan buena como la del problema B. La reducción estricta conserva la pertenencia tanto a PTAS como a APX.

Existe un concepto similar de reducción S, para el cual $c_{A}(x,y)=c_{B}(x',y')$ Además, los óptimos de las dos instancias correspondientes deben tener el mismo costo. La S-reducción es un caso muy especial de reducción estricta, y resulta aún más restrictiva. En efecto, los dos problemas A y B deben estar en correspondencia casi perfecta. La existencia de una S-reducción implica no solo la existencia de una reducción estricta, sino también cualquier otra reducción aquí mencionada.

L-reducción

Las reducciones L conservan la pertenencia a PTAS y APX (pero solo para problemas de minimización en el caso de este último ). En consecuencia, no pueden utilizarse en general para demostrar resultados de completitud sobre APX, Log-APX o Poly-APX, pero no obstante se valoran por su formulación natural y facilidad de uso en las demostraciones. ^{[ 1 ]}

Reducción de PTAS

La reducción PTAS es otro esquema de reducción comúnmente utilizado. Si bien conserva la pertenencia a PTAS, no lo hace para APX. Sin embargo, la completitud de APX se define en términos de reducciones PTAS.

Las reducciones PTAS son una generalización de las reducciones P, que se muestran a continuación, con la única diferencia de que se permite que la función $g$ dependa de la razón de aproximación $r$ .

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 demostrar la pertenencia a APX y PTAS, respectivamente. Ambos introducen una nueva función $c$ , definida sobre números mayores que 1, que debe ser computable.

En una reducción A, tenemos que

R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq c(r)

.

En una reducción P, tenemos que

R_{B}(x',y')\leq c(r)\rightarrow R_{A}(x,y)\leq r

.

La existencia de una reducción P implica la existencia de una reducción PTAS.

Reducción de electrones

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 preserva la pertenencia no solo a PTAS y APX, sino también a las clases más amplias Log-APX y Poly-APX . La reducción E introduce dos nuevos parámetros, un polinomio $p$ y una constante. $\beta$ Su definición es la siguiente.

En una reducción E, tenemos que para algún polinomio $p$ y constante $\beta$ ,

$c_{B}({\text{OPT}}_{B}(x'))\leq p(|x|)c_{A}({\text{OPT}}_{A}(x))$ , dónde $|x|$ indica el tamaño de la descripción de la instancia del problema.
Para cualquier solución $y'$ a $B$ , tenemos $R_{A}(x,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)$ .

Para obtener una reducción A a partir de una reducción E, sea $c(r)=1+\beta \cdot (r-1)$ y para obtener una reducción P a partir de una reducción E, sea $c(r)=1+(r-1)/\beta$ .

reducción de AP

Las reducciones AP se utilizan para definir la completitud en las clases Log-APX y Poly-APX . Son un caso especial de reducción PTAS, que cumple las siguientes restricciones.

En una reducción AP, tenemos que para alguna constante $\alpha$ ,

R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq 1+\alpha \cdot (r-1)

con la generalización adicional de que se permite que la función $g$ dependa de la razón de aproximación $r$ , como en la reducción PTAS.

La reducción AP es también una generalización de la reducción E. De hecho, es necesario imponer una restricción adicional para que la reducción AP preserve la pertenencia a Log-APX y Poly-APX, como lo hace la reducción E: para un tamaño de problema fijo, el tiempo de cálculo de $f y g$ debe ser no creciente a medida que aumenta la razón de aproximación.

Reducción de brechas

Una reducción de brecha es un tipo de reducción que, si bien es útil para demostrar algunos resultados de inaproximabilidad, no se asemeja a las demás reducciones que se muestran aquí. Las reducciones de brecha abordan problemas de optimización dentro de un contenedor de problemas de decisión, generado al cambiar el objetivo del problema a distinguir entre la solución óptima y soluciones que son un factor multiplicativo peor que la óptima.

Véase también

Referencias

1 2 Crescenzi, Pierluigi (1997). "Una breve guía para reducciones que preservan la aproximación" . Actas de la Duodécima Conferencia Anual del IEEE sobre Complejidad Computacional. Washington, DC: IEEE Computer Society. págs. 262–. doi : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7. S2CID 18911241 .

[crescenzi-1] 1 2 Crescenzi, Pierluigi (1997). "Una breve guía para reducciones que preservan la aproximación" . Actas de la Duodécima Conferencia Anual del IEEE sobre Complejidad Computacional. Washington, DC: IEEE Computer Society. págs. 262–. doi : 10.1109/CCC.1997.612321 . ISBN 0-8186-7907-7. S2CID 18911241 .

[ 1 ]