L-redukce - L-reduction

v počítačová věda, zejména studium aproximační algoritmy, an L-redukce ("lineární redukce") je transformace optimalizační problémy který lineárně zachovává vlastnosti přibližnosti; je to jeden typ redukce zachovávající aproximaci. L-redukce ve studiích přibližnosti optimalizační problémy hrají podobnou roli jako polynomiální redukce ve studiích výpočetní složitost z rozhodovací problémy.

Termín L redukce se někdy používá k označení redukce log prostoru, analogicky s třídou složitosti L, ale toto je jiný koncept.

Definice

Nechť jsou A a B. optimalizační problémy a c_A a c_B jejich příslušné nákladové funkce. Dvojice funkcí F a G je redukce L, pokud jsou splněny všechny následující podmínky:

funkce F a G jsou vypočítatelné v polynomiální čas,
-li X je tedy příkladem problému A F(X) je příkladem problému B,
-li y ' je řešením F(X), pak G(y ' ) je řešením X,
existuje kladná konstanta α taková, že

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

,

existuje kladná konstanta β taková, že pro každé řešení y ' na F(X)

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

.

Vlastnosti

Důsledek snížení PTAS

Redukce L z problému A na problém B znamená AP-redukce když A a B jsou problémy s minimalizací a a Snížení PTAS když A a B jsou problémy s maximalizací. V obou případech, když B má PTAS a dochází k L-redukci z A na B, pak A má také PTAS.^[1]^[2] To umožňuje použití redukce L jako náhrady za prokázání existence redukce PTAS; Crescenzi navrhl, že přirozenější formulace redukce L je ve skutečnosti v mnoha případech užitečnější kvůli snadnému použití.^[3]

Důkaz (minimalizační případ)

Nechť je aproximační poměr B. ${displaystyle 1 + delta}$ .Začněte aproximačním poměrem A, ${displaystyle {frac {c_ {A} (y)} {mathrm {OPT} _ {A} (x)}}}$ . Můžeme odstranit absolutní hodnoty kolem třetí podmínky definice redukce L, protože víme, že A a B jsou problémy s minimalizací. Tuto podmínku nahraďte dosažením

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

Zjednodušení a nahrazení první podmínky máme

{displaystyle {frac {c_ {A} (y)} {mathrm {OPT} _ {A} (x)}} leq 1 + alfa eta left ({frac {c_ {B} (y ') - mathrm {OPT} _ {B} (x ')} {mathrm {OPT} _ {B} (x')}} ight)}

Ale výraz v závorkách na pravé straně se ve skutečnosti rovná ${displaystyle delta}$ . Aproximační poměr A je tedy ${displaystyle 1 + alfa eta delta}$ .

To splňuje podmínky pro redukci AP.

Důkaz (případ maximalizace)

Nechť je aproximační poměr B. ${displaystyle {frac {1} {1-delta '}}}$ .Začněte aproximačním poměrem A, ${displaystyle {frac {c_ {A} (y)} {mathrm {OPT} _ {A} (x)}}}$ . Můžeme odstranit absolutní hodnoty kolem třetí podmínky definice L-redukce, protože víme, že A a B jsou problémy s maximalizací. Tuto podmínku nahraďte dosažením

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

Zjednodušení a nahrazení první podmínky máme

{displaystyle {frac {c_ {A} (y)} {mathrm {OPT} _ {A} (x)}} geq 1-alfa eta left ({frac {c_ {B} (y ') - mathrm {OPT} _ {B} (x ')} {mathrm {OPT} _ {B} (x')}} ight)}

Ale výraz v závorkách na pravé straně se ve skutečnosti rovná ${displaystyle delta '}$ . Aproximační poměr A je tedy ${displaystyle {frac {1} {1-alpha eta delta '}}}$ .

Li ${displaystyle {frac {1} {1-alpha eta delta '}} = 1 + epsilon}$ , pak ${displaystyle {frac {1} {1-delta '}} = 1+ {frac {epsilon} {alfa eta (1 + epsilon) -epsilon}}}$ , který splňuje požadavky na redukci PTAS, ale nikoli redukci AP.

Další vlastnosti

Snížení L také znamená P-redukce.^[3] Lze odvodit, že redukce L znamenají redukce PTAS z této skutečnosti a skutečnost, že redukce P implikují redukce PTAS.

L-redukce zachovávají členství v APX pouze pro minimalizační případ, což je důsledkem implikací AP-redukcí.

Příklady

Dominující sada: příklad s α = β = 1
Překonfigurování tokenu: příklad s α = 1/5, β = 2

Viz také

Reference

^ Kann, Viggo (1992). K problémům s imitací NP-complete mathrm {OPT}. Královský technologický institut, Švédsko. ISBN 978-91-7170-082-7.
^ Christos H. Papadimitriou; Mihalis Yannakakis (1988). "mathrm {OPT} imizace, třídy aproximace a složitosti". STOC '88: Sborník z dvacátého ročníku ACM Symposium on Theory of Computing. doi:10.1145/62212.62233.
^ ^A ^b Crescenzi, Pierluigi (1997). „Krátký průvodce snižováním aproximace“. Sborník příspěvků z 12. výroční konference IEEE o výpočetní složitosti. Washington, D.C .: IEEE Computer Society: 262–.

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Složitost a aproximace. Problémy kombinatorické optimalizace a jejich vlastnosti přibližnosti. 1999, Springer. ISBN 3-540-65431-3

P ≟ NP

Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[Kann92-1] Kann, Viggo (1992). K problémům s imitací NP-complete mathrm {OPT}. Královský technologický institut, Švédsko. ISBN 978-91-7170-082-7.

[Papadimitriou88-2] Christos H. Papadimitriou; Mihalis Yannakakis (1988). "mathrm {OPT} imizace, třídy aproximace a složitosti". STOC '88: Sborník z dvacátého ročníku ACM Symposium on Theory of Computing. doi:10.1145/62212.62233.

[crescenzi-3] A ^b Crescenzi, Pierluigi (1997). „Krátký průvodce snižováním aproximace“. Sborník příspěvků z 12. výroční konference IEEE o výpočetní složitosti. Washington, D.C .: IEEE Computer Society: 262–.

[1]

[2]

[3]