Likimääräinen polynomiaikakaavio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Matematiikassa polynomiajan approksimaatiomalli tai polynomiajan approksimaatiomalli (PTAS ) tarkoittaa luokkaa likimääräisiä polynomiaikaisia ​​​​algoritmeja yleisesti NP-kovien optimointiongelmien ratkaisemiseksi. Jos P = NP, tämän käsitteen käyttöönotto menettää merkityksensä. Siksi oletamme edelleen, että Р ei ole sama kuin NP. Ja menettämättä yleisyyttä, määrittelemme minimointiongelman käsitteen.

Määritelmä

PTAS on algoritmiperhe, joka riippuu parametrista ε siten, että jonkin optimointitehtävän mielivaltaiselle datajoukolle ja parametrille ε > 0, perheen algoritmi löytää ratkaisun polynomiajassa tavoitefunktiolla S < (1 + ε)OPT, jossa OPT on tavoitefunktion minimi. Esimerkiksi matkustavan myyjän ongelmalle euklidisessa avaruudessa on olemassa PTAS, joka löytää läpikulkupolun, jonka pituus on enintään (1 + ε) L , missä L on lyhimmän polun pituus. [yksi]

PTAS:n suoritusajan tulee riippua polynomiaalisesti n :stä minkä tahansa kiinteän ε:n kohdalla, mutta se voi vaihdella mielivaltaisesti ε:n muuttuessa. Algoritmit, joiden käyntiaika on O ( n 1/ε ) tai jopa O ( n exp(1/ε) ), ovat PTAS-algoritmeja.

Deterministiset algoritmit

PTAS-algoritmeissa monimutkaisuuden arvioinnin eksponentti voi kasvaa katastrofaalisesti ε:n pienentyessä, esimerkiksi kun suoritusaika on O( n (1/ε)! ), mikä tekee tästä algoritmiryhmästä käytännön näkökulmasta vähän kiinnostavaa. . Voidaan määritellä tehokas polynomi-ajan approksimaatiomenetelmä tai tehokas polynomi-ajan approksimaatiomenetelmä ( EPTAS ), jonka kulkuajan tulee olla O (nc), jossa vakio c on riippumaton ε : stä . Tämä varmistaa, että syöttödatan koon kasvattaminen lisää suoritusaikaa ε:n arvosta riippumatta; kuitenkin O -merkin alla oleva tekijä riippuu edelleen mielivaltaisesti ε:stä. Toinen käytännössä hyödyllisempi rajoite on täysin polynomi-ajan approksimaatiomalli ( FPTAS ), joka edellyttää, että algoritmin ajoaika riippuu polynomiaalisesti sekä ongelman koosta n että 1/ε. Esimerkki ongelmasta, jota varten FPTAS on olemassa, on reppuongelma . Mutta ei ole edes PTAS :ta tähän liittyvään konttiongelmaan .

Millä tahansa vahvasti NP-kovalla optimointiongelmalla polynomirajoitteisella tavoitefunktiolla ei voi olla FPTAS:a. [2] Päinvastoin ei kuitenkaan pidä paikkaansa. 2D -reppuongelma ei ole vahvasti NP-kova, mutta sillä ei ole FPTAS:ta, vaikka tavoitefunktio olisi polynomirajallinen. [3]

Suorita FPTAS ⊊ PTAS ⊊  APX . Siksi APX-kovissa ongelmissa ei ole PTAS:ta.

Toinen PTAS:n muunnos on kvasipolynomi -ajan approksimaatiomalli ( QPTAS ) . QPTAS on aika monimutkainen kaikille kiinteille .

Satunnaistetut algoritmit

Joissakin ongelmissa, joissa ei ole PTAS:ta, voi olla satunnaistettuja algoritmeja , joilla on samanlaiset ominaisuudet - polynomi-aika satunnaistettu approksimaatiomalli tai polynomi-aika satunnaistettu approksimaatiomalli ( PRAS ). PRAS-algoritmi parametrilla ε > 0 optimointitehtävän mielivaltaiselle tietojoukolle löytää polynomiajassa suurella todennäköisyydellä ratkaisun, joka ei ylitä (1 + ε)OPT. Tyypillisesti "suuri todennäköisyys" tarkoittaa todennäköisyyttä, joka on suurempi kuin 3/4, vaikka määritelmä ei määrittele tätä arvoa. Kuten PTAS-algoritmilla, myös PRAS-algoritmilla on oltava ajoaika, joka riippuu polynomiaalisesti arvosta n , mutta ei 1/ε:stä. Analogisesti determinististen algoritmien kanssa otetaan käyttöön EPTAS :n kaltainen EPRAS ja FPTAS :n kaltainen FPRAS. [2]

Muistiinpanot

  1. ↑ Sanjeev Arora , Euklidisen TSP:n ja muiden geometristen ongelmien polynomiajan approksimaatiokaaviot, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 2 Vazirani, Vijay V. Approksimaatioalgoritmit  (epämääräinen) . - Berliini: Springer, 2003. - S.  294-295 . — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer ja U. Pferschy ja D. Pisinger. Reppuongelmat  (neopr.) . - Springer, 2004.

Linkit