Reducción L

En informática , particularmente en el estudio de algoritmos de aproximación , una L-reducción (" reducción lineal ") es una transformación de problemas de optimización que preserva linealmente las características de aproximabilidad; es un tipo de reducción que preserva la aproximación . Las L-reducciones en estudios de aproximabilidad de problemas de optimización juegan un papel similar al de las reducciones polinómicas en los estudios de complejidad computacional de problemas de decisión .

El término reducción L se utiliza a veces para referirse a reducciones del espacio logarítmico , por analogía con la clase de complejidad L , pero este es un concepto diferente.

Definición

Sean A y B problemas de optimización y c _A y c _B sus respectivas funciones de costo. Un par de funciones f y g es una L-reducción si se cumplen todas las siguientes condiciones:

Las funciones f y g son computables en tiempo polinomial ,
si x es una instancia del problema A, entonces f ( x ) es una instancia del problema B,
si y' es una solución de f ( x ), entonces g ( y' ) es una solución de x ,
existe una constante positiva α tal que

\mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)

,

existe una constante positiva β tal que para cada solución y' a f ( x )

|\mathrm {OPT_{A}} (x)-c_{A}(g(y'))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y')|

.

Propiedades

Implicación de la reducción del PTAS

Una reducción L del problema A al problema B implica una reducción AP cuando A y B son problemas de minimización y una reducción PTAS cuando A y B son problemas de maximización. En ambos casos, cuando B tiene una PTAS y hay una reducción L de A a B, entonces A también tiene una PTAS. ^[1]^[2] Esto permite el uso de la reducción L como reemplazo para demostrar la existencia de una reducción PTAS; Crescenzi ha sugerido que la formulación más natural de la reducción L es en realidad más útil en muchos casos debido a la facilidad de uso. ^[3]

Prueba (caso de minimización)

Sea la razón de aproximación de B . Comencemos con la razón de aproximación de A, . Podemos eliminar los valores absolutos alrededor de la tercera condición de la definición de reducción L ya que sabemos que A y B son problemas de minimización. Sustituyamos esa condición para obtener $1+\delta$ ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq {\frac {\mathrm {OPT} _{A}(x)+\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Simplificando y sustituyendo la primera condición, tenemos

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\leq 1+\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

Pero el término entre paréntesis en el lado derecho en realidad es igual a . Por lo tanto, la razón de aproximación de A es . $\delta$ $1+\alpha \beta \delta$

Esto cumple las condiciones para la reducción de AP.

Prueba (caso de maximización)

Sea la razón de aproximación de B . Comencemos con la razón de aproximación de A, . Podemos eliminar los valores absolutos alrededor de la tercera condición de la definición de reducción L ya que sabemos que A y B son problemas de maximización. Sustituyamos esa condición para obtener ${\frac {1}{1-\delta '}}$ ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq {\frac {\mathrm {OPT} _{A}(x)-\beta (c_{B}(y')-\mathrm {OPT} _{B}(x'))}{\mathrm {OPT} _{A}(x)}}

Simplificando y sustituyendo la primera condición, tenemos

{\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}\geq 1-\alpha \beta \left({\frac {c_{B}(y')-\mathrm {OPT} _{B}(x')}{\mathrm {OPT} _{B}(x')}}\right)

Pero el término entre paréntesis en el lado derecho en realidad es igual a . Por lo tanto, la razón de aproximación de A es . $\delta '$ ${\frac {1}{1-\alpha \beta \delta '}}$

Si , entonces , que cumple los requisitos para la reducción de PTAS pero no para la reducción de AP. ${\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon$ ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$

Otras propiedades

Las reducciones L también implican reducciones P. ^[3] Se puede deducir que las reducciones L implican reducciones PTAS a partir de este hecho y del hecho de que las reducciones P implican reducciones PTAS.

Las reducciones L preservan la pertenencia a APX solo para el caso minimizador, como resultado de implicar reducciones AP.

Ejemplos

Conjunto dominante : un ejemplo con α = β = 1
Reconfiguración de tokens : un ejemplo con α = 1/5, β = 2

Véase también

Referencias

^ Kann, Viggo (1992). Sobre la aproximabilidad de problemas de optimización NP-completos . Instituto Real de Tecnología, Suecia. ISBN 978-91-7170-082-7.
^ Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\mathrm{OPT}imización, aproximación y clases de complejidad". STOC '88: Actas del vigésimo simposio anual de la ACM sobre teoría de la computación . doi : 10.1145/62212.62233 .
^ ab 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. pp. 262–. doi :10.1109/CCC.1997.612321. ISBN 9780818679070.S2CID18911241 .

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complejidad y aproximación. Problemas de optimización combinatoria y sus propiedades de aproximación. 1999, Springer. ISBN 3-540-65431-3

[Kann92-1] Kann, Viggo (1992). Sobre la aproximabilidad de problemas de optimización NP-completos . Instituto Real de Tecnología, Suecia. ISBN 978-91-7170-082-7.

[Papadimitriou88-2] Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\mathrm{OPT}imización, aproximación y clases de complejidad". STOC '88: Actas del vigésimo simposio anual de la ACM sobre teoría de la computación . doi : 10.1145/62212.62233 .

[crescenzi-3] 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. pp. 262–. doi :10.1109/CCC.1997.612321. ISBN 9780818679070.S2CID18911241 .