L-valettu

L-pelkistys (tekstistä " lineaarinen " = " lineaarinen ") - optimointiongelmien muunnos , jossa approksimoinnin ominaisuudet säilyvät lineaarisesti; on eräänlainen approksimaatiota säilyttävä cast . L-pelkistys tutkittaessa mahdollisuutta approksimoida optimointiongelmia näyttelee samanlaista roolia kuin polynomipelkistys tutkittaessa ratkaistavuusongelmien laskennallista monimutkaisuutta .

Mahdollisuutta L-pelkistää yksi ongelma toiseksi kutsutaan L-pelkistyvyydeksi [1] .

Termiä " L-pelkistys " käytetään joskus viittaamaan pelkistykseen logaritmiseen avaruuteen analogisesti kompleksisuusluokan L kanssa, mutta tämä on täysin erilainen käsite.[ määritä ] .

Määritelmä

Olkoot A ja B kaksi optimointitehtävää ja c A ja c B niiden tavoitefunktioita. F- ja g - funktiopari on L-pelkistys, jos kaikki seuraavat ehdot täyttyvät:

funktiot f ja g voidaan laskea polynomiajassa ,
jos x on tehtävän A esiintymä, niin f ( x ) on tehtävän B esiintymä,
jos y' on f ( x ) ratkaisu, niin g ( y' ) on x :n ratkaisu ,
on sellainen positiivinen vakio α, että

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

on olemassa sellainen positiivinen vakio β, että millä tahansa ratkaisulla y' funktiolle f ( x )

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

Ominaisuudet

Suhde PTAS-valuon

L-pelkistys ongelmasta A ongelmaan B sisältää AP-vähennyksen , jos A ja B ovat minimointiongelmia, ja PTAS-vähennyksen , jos A ja B ovat maksimointiongelmia. Molemmissa tapauksissa, jos ongelmalla B on PTAS ja L-pelkistys A:sta B:hen, niin A:lla on myös PTAS [2] [3] . Tämä mahdollistaa L-valun käyttämisen PTAS-valun olemassaolon todistamisen sijaan. Crescenzi ehdotti, että L-pelkistyksen luonnollisempi formulaatio on itse asiassa hyödyllisempi monissa tapauksissa käytön helppouden vuoksi [4] .

Todistus (minimointitapaus)

Olkoon tehtävän B approksimaatiokerroin yhtä suuri kuin . Aloitetaan tehtävän A approksimaatiokertoimella, joka on yhtä suuri kuin . Voit jättää itseisarvosulut pois L-vähennyksen määritelmistä (toinen kaava), koska A ja B ovat minimointiongelmia. Korvaamme tämän ehdon tehtävän A kertoimella ja saamme $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)))

Ensimmäisen kaavan yksinkertaistamisen ja korvaamisen jälkeen saamme

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

Mutta oikealla puolella oleva suluissa oleva termi on itse asiassa yhtä suuri kuin . Siten tehtävän A approksimaatiokerroin on yhtä suuri kuin . $\delta$ $1+\alpha \beta \delta$

Ja tämä täyttää AP-vähennyksen ehdot.

Todiste (maksimointitapaus)

Olkoon tehtävän B approksimaatiokerroin yhtä suuri kuin . Aloitetaan tehtävän A approksimaatiokertoimella, joka on yhtä suuri kuin . Voit jättää itseisarvosulut pois toisesta kaavasta L-vähennyksen määritelmästä, koska A ja B ovat maksimointiongelmia. Korvaamalla tämän ehdon saamme ${\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)))

Ensimmäisen kaavan yksinkertaistamisen ja korvaamisen jälkeen saamme

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

Mutta oikealla puolella oleva suluissa oleva termi on itse asiassa yhtä suuri kuin . Siten tehtävän A approksimaatiokerroin on yhtä suuri kuin . $\delta '$ ${\frac {1}{1-\alpha \beta \delta '}}$

Jos , niin , joka täyttää PTAS-valinnan vaatimukset, mutta ei AP-valittua. ${\frac {1}{1-\alpha \beta \delta '}}=1+\epsilon$ ${\frac {1}{1-\delta '}}=1+{\frac {\epsilon }{\alpha \beta (1+\epsilon )-\epsilon }}$

Muut ominaisuudet

L-cast sisältää myös P-valon [4] . Tästä tosiasiasta ja siitä tosiasiasta, että P-vähennys merkitsee PTAS-vähennystä, voidaan päätellä, että L-vähennys aiheuttaa PTAS-vähenemisen.

L-vähennys säilyttää jäsenyyden APX:ssä vain minimoinnin tapauksessa, koska tässä tapauksessa AP-vähennys seuraa L-vähennyksestä.

Esimerkkejä

Dominoiva joukko : esimerkki jossa α = β = 1
Markkerin uudelleenkonfigurointiongelma : esimerkki, jossa α = 1/5, β = 2

Katso myös

MAXSNP
Lähentäminen säilyttävä vähennys
PTAS cast

Kirjallisuus

Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M.. Monimutkaisuus ja lähentäminen. Kombinatoriset optimointiongelmat ja niiden approksimaatioominaisuudet - Springer, 1999. - ISBN 3-540-65431-3 .
Crescenzi, Pierluigi. Lyhyt opas Approximation Preserving Reductions // Proceedings of the 12th Annual IEEE Conference on Computational Complexity. -Washington, DC, 1997.
Kann, Viggo. . NP-täydellisten \mathrm{OPT}imisointiongelmien lähentävyydestä. - Royal Institute of Technology, Ruotsi, 1992. - ISBN 91-7170-082-X .
Papadimitriou C. H., Yannakakis M. . STOC '88: Kahdennenkymmenennen vuotuisen ACM-symposiumin julkaisut tietojenkäsittelyteoriasta. - 1988. - doi : 10.1145/62212.62233 .
Sviridenko Maksim Ivanovitš Algoritmit, joissa on arvioita erillisistä sijaintiongelmista. - Novosibirsk, 1998. - (väitöskirja).