Reducción en 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

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

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

${\displaystyle |\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 ${\displaystyle 1+\delta }$ ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$

${\displaystyle {\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

${\displaystyle {\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 . ${\displaystyle \delta }$ ${\displaystyle 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 ${\displaystyle {\frac {1}{1-\delta '}}}$ ${\displaystyle {\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}}$

${\displaystyle {\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

${\displaystyle {\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 . ${\displaystyle \delta '}$ ${\displaystyle {\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. ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon }$ ${\displaystyle {\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

• SNP máximo
• Reducción que preserva la aproximación
• Reducción de PTAS

Referencias

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.
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 .
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. Número de identificación del sujeto  18911241.

• 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