En ciencias de la computación , 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 conserva linealmente características de aproximación; es un tipo de reducción que conserva la aproximación . Las L-reducciones en estudios de aproximabilidad de problemas de optimización juegan un papel similar al de las reducciones polinomiales en los estudios de complejidad computacional de problemas de decisión .
El término reducción L se usa a veces para referirse a reducciones de 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 calculables 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
- ,
- existe una constante positiva β tal que para cada solución y' a f ( x )
- .
Propiedades
Implicación de la reducción de 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 un PTAS y hay una reducción L de A a B, entonces A también tiene un PTAS. [1] [2] Esto permite el uso de la reducción L como un reemplazo para mostrar la existencia de una reducción PTAS; Crescenzi ha sugerido que la formulación más natural de L-reducción 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 . Comience 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. Sustituya esa condición para obtener
Simplificando y sustituyendo la primera condición, tenemos
Pero el término entre paréntesis en el lado derecho en realidad es igual a . Por tanto, la razón de aproximación de A es.
Esto cumple las condiciones para la reducción de AP.
Prueba (caso de maximización)
Sea la razón de aproximación de B . Comience 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. Sustituya esa condición para obtener
Simplificando y sustituyendo la primera condición, tenemos
Pero el término entre paréntesis en el lado derecho en realidad es igual a . Por tanto, la razón de aproximación de A es.
Si , luego , que cumple con los requisitos de reducción de PTAS pero no de reducción de AP.
Otras propiedades
L-reducciones también implican P-reducción . [3] Se puede deducir que las reducciones L implican reducciones de PTAS a partir de este hecho y el hecho de que las reducciones P implican reducciones de PTAS.
Las reducciones L preservan la membresía en APX solo para el caso de minimización, como resultado de implicar reducciones de AP.
Ejemplos de
- Conjunto dominante : un ejemplo con α = β = 1
- Reconfiguración de tokens : un ejemplo con α = 1/5, β = 2
Ver también
Referencias
- ^ Kann, Viggo (1992). Sobre la aproximación de problemas de imización NP-complete \ mathrm {OPT} . Real Instituto de Tecnología, Suecia. ISBN 978-91-7170-082-7.
- ^ Christos H. Papadimitriou; Mihalis Yannakakis (1988). "\ mathrm {OPT} clases de imitación, aproximación y complejidad". STOC '88: Actas del vigésimo simposio anual ACM sobre teoría de la computación . doi : 10.1145 / 62212.62233 .
- ^ 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–.
- 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 aproximabilidad. 1999, Springer. ISBN 3-540-65431-3