L-reduktion

Inom datavetenskap , särskilt studiet av approximationsalgoritmer , är en L-reduktion (" linjär reduktion ") en transformation av optimeringsproblem som linjärt bevarar approximationsegenskaper; det är en typ av approximationsbevarande reduktion . L-reduktioner i studier av approximation av optimeringsproblem spelar en liknande roll som polynomreduktioner i studier av beräkningskomplexitet av beslutsproblem .

Termen L-reduktion används ibland för att hänvisa till log-space-reduktioner, i analogi med komplexitetsklassen L , men detta är ett annat koncept.

Definition

Låt A och B vara optimeringsproblem och c _A och c _B deras respektive kostnadsfunktioner. Ett par funktioner f och g är en L-reduktion om alla följande villkor är uppfyllda:

funktionerna f och g är beräkningsbara i polynomtid ,
om x är en instans av problem A, då är f ( x ) en instans av problem B,
om y' är en lösning till f ( x ), så är g ( y' ) en lösning till x ,
det finns en positiv konstant α sådan att

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

,

det finns en positiv konstant β så att för varje lösning y' till f ( x )

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

.

Egenskaper

Implikation av PTAS-reduktion

En L-reduktion från problem A till problem B innebär en AP-reduktion när A och B är minimeringsproblem och en PTAS-reduktion när A och B är maximeringsproblem. I båda fallen, när B har en PTAS och det finns en L-reduktion från A till B, då har A också en PTAS. Detta möjliggör användningen av L-reduktion som en ersättning för att visa förekomsten av en PTAS-reduktion; Crescenzi har föreslagit att den mer naturliga formuleringen av L-reduktion faktiskt är mer användbar i många fall på grund av enkel användning.

Bevis (minimeringsfall)

Låt approximationsförhållandet för B vara $1+\delta$ . Börja med approximationsförhållandet för A, ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$ . Vi kan ta bort absoluta värden kring det tredje villkoret i L-reduktionsdefinitionen eftersom vi vet att A och B är minimeringsproblem. Ersätt det villkoret för att få

{\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)}}

Att förenkla och ersätta det första villkoret har vi

{\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)

Men termen inom parentes på höger sida är faktiskt lika med $\delta$ . Sålunda är approximationsförhållandet för A $1+\alpha \beta \delta$ .

Detta uppfyller villkoren för AP-reduktion.

Bevis (maximeringsfall)

Låt approximationsförhållandet för B vara ${\frac {1}{1-\delta '}}$ . Börja med approximationsförhållandet för A, ${\frac {c_{A}(y)}{\mathrm {OPT} _{A}(x)}}$ . Vi kan ta bort absoluta värden kring det tredje villkoret i L-reduktionsdefinitionen eftersom vi vet att A och B är maximeringsproblem. Ersätt det villkoret för att få

{\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)}}

Att förenkla och ersätta det första villkoret har vi

{\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)

Men termen inom parentes på höger sida är faktiskt lika med $\delta '$ . Sålunda är approximationsförhållandet för A ${\frac {1}{1-\alpha \beta \delta '}}$ .

Om ${\displaystyle {\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon } ,$ då är ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$ , som uppfyller kraven för PTAS-reduktion men inte AP-reduktion.

Övriga fastigheter

L-reduktioner innebär också P-reduktion . Man kan sluta sig till att L-reduktioner innebär PTAS-reduktioner av detta faktum och det faktum att P-reduktioner innebär PTAS-reduktioner.

L-reduktioner behåller medlemskap i APX endast för det minimerande fallet, som ett resultat av att implicera AP-reduktioner.

Exempel

Dominerande mängd : ett exempel med α = β = 1
Token omkonfiguration : ett exempel med α = 1/5, β = 2

Se även

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Komplexitet och approximation. Kombinatoriska optimeringsproblem och deras approximationsegenskaper. 1999, Springer. ISBN 3-540-65431-3