L-støbt

L-reduktion (fra " lineær " = " lineær ") - transformation af optimeringsproblemer , hvor egenskaberne ved tilnærmelse er lineært bevaret; er en slags tilnærmelsesbevarende cast . L-reduktionen ved at studere muligheden for at approksimere optimeringsproblemer spiller en lignende rolle som polynomiereduktionen spiller ved at studere den beregningsmæssige kompleksitet af løselighedsproblemer .

Muligheden for at L-reducere et problem til et andet kaldes L-reducerbarhed [1] .

Udtrykket " L-reduktion " bruges nogle gange til at referere til en reduktion til et logaritmisk rum i analogi med kompleksitetsklassen L , men dette er et helt andet koncept.[ angiv ] .

Definition

Lad A og B være to optimeringsproblemer og c A og c B være deres objektive funktioner. Et par funktioner f og g er en L-reduktion, hvis alle følgende betingelser er sande:

funktionerne f og g kan beregnes i polynomisk tid ,
hvis x er en forekomst af opgave A, så er f ( x ) en forekomst af opgave B,
hvis y' er løsningen for f ( x ), så er g ( y' ) løsningen for x ,
der er en positiv konstant α sådan, at

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

der er en positiv konstant β, således at for enhver løsning y' for f ( x )

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

Egenskaber

Forholdet til PTAS-casting

En L-reduktion fra problem A til problem B medfører en AP-reduktion hvis A og B er minimeringsproblemer, og en PTAS-reduktion hvis A og B er maksimeringsproblemer. I begge tilfælde, hvis problem B har PTAS og der er en L-reduktion fra A til B, så har A også PTAS [2] [3] . Dette gør det muligt at bruge L-støbningen i stedet for at bevise eksistensen af en PTAS-støbning. Crescenzi foreslog, at den mere naturlige formulering af L-reduktionen faktisk er mere nyttig i mange tilfælde på grund af brugervenlighed [4] .

Bevis (tilfælde af minimering)

Lad tilnærmelseskoefficienten for opgave B være lig med . Lad os starte med tilnærmelseskoefficienten for opgave A, lig med . Du kan droppe de absolutte værdiparenteser i definitionerne af L-reduktionen (anden formel), fordi A og B er minimeringsproblemer. Vi erstatter denne betingelse i koefficienten for opgave A og opnår $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)))

Efter at have forenklet og erstattet den første formel, får 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 udtrykket i parentes i højre side er i virkeligheden lig med . Således er tilnærmelseskoefficienten for opgave A lig med . $\delta$ $1+\alpha \beta \delta$

Og det opfylder betingelserne for AP-reduktionen.

Bevis (maksimeringssag)

Lad tilnærmelseskoefficienten for opgave B være lig med . Lad os starte med tilnærmelseskoefficienten for opgave A, lig med . Du kan udelade de absolutte værdiparenteser i den anden formel for definitionen af L-reduktion, da A og B er maksimeringsproblemer. Ved at erstatte denne betingelse får vi ${\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)))

Efter at have forenklet og erstattet den første formel, får 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 udtrykket i parentes i højre side er i virkeligheden lig med . Således er tilnærmelseskoefficienten for opgave A lig med . $\delta '$ ${\frac {1}{1-\alpha \beta \delta '}}$

Hvis , så , som opfylder kravene til PTAS-castet, men ikke AP-castet. ${\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon$ ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$

Andre egenskaber

Et L-kast medfører også et P-kast [4] . Det kan udledes, at en L-reduktion medfører en PTAS-reduktion af dette faktum og af, at en P-reduktion medfører en PTAS-reduktion.

L-reduktionen bevarer kun medlemskab af APX i tilfælde af minimering, da AP-reduktionen i dette tilfælde følger af L-reduktionen.

Eksempler

Dominerende mængde : eksempel med α = β = 1
Markørrekonfigurationsproblem : eksempel med α = 1/5, β = 2

Se også

MAXSNP
Tilnærmelsesbevarende reduktion
PTAS cast

Litteratur

Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M.. Kompleksitet og tilnærmelse. Kombinatoriske optimeringsproblemer og deres tilnærmelsesegenskaber - Springer, 1999. - ISBN 3-540-65431-3 .
Crescenzi, Pierluigi. En kort guide til tilnærmelse til bevarelse af reduktioner // Proceedings of the 12th Annual IEEE Conference on Computational Complexity. -Washington, DC, 1997.
Kann, Viggo. . Om tilnærmeligheden af NP-komplette \mathrm{OPT}imiseringsproblemer. - Royal Institute of Technology, Sverige, 1992. - ISBN 91-7170-082-X .
Papadimitriou C. H., Yannakakis M. . STOC '88: Proceedings af det tyvende årlige ACM Symposium on Theory of Computing. - 1988. - doi : 10.1145/62212.62233 .
Sviridenko Maxim Ivanovich Algoritmer med estimater for diskrete lokaliseringsproblemer. - Novosibirsk, 1998. - (Afhandling).