Hozzávetőleges polinomiális időséma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. április 12-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A matematikában a polinomidő-közelítési séma vagy a polinomidő-közelítési séma ( PTAS ) közelítő polinomidő- algoritmusok osztályát jelöli általában NP-nehéz optimalizálási problémák megoldására. Ha P = NP, akkor ennek a fogalomnak a bevezetése értelmét veszti. Ezért a továbbiakban azt feltételezzük, hogy Р nem esik egybe NP-vel. És az általánosság elvesztése nélkül definiáljuk a minimalizálási probléma fogalmát.

Definíció

A PTAS egy olyan algoritmuscsalád, amely az ε paramétertől függ, így valamilyen optimalizálási probléma tetszőleges adathalmazára ε > 0 paraméter esetén a család algoritmusa polinomiális időben talál megoldást az S < (1 +) célfüggvénnyel. ε)OPT, ahol OPT a célfüggvény minimuma. Például az utazó eladó problémájára az euklideszi térben létezik egy PTAS, amely legfeljebb (1 + ε) L hosszúságú bejárási utat talál , ahol L a legrövidebb út hossza. [egy]

A PTAS végrehajtási idejének polinomiálisan kell függnie n -től bármely rögzített ε esetén, de tetszőlegesen változhat, ahogy ε változik. Az O ( n 1/ε ) vagy akár O ( n exp(1/ε) ) futásidejű algoritmusok PTAS algoritmusok.

Determinisztikus algoritmusok

A PTAS algoritmusokban a komplexitásbecslésben a kitevő katasztrofálisan nőhet ε csökkenésével, például ha a végrehajtási idő O( n (1/ε)! ), ami gyakorlati szempontból kevéssé érdekli ezt az algoritmusosztályt. . Definiálhatunk egy hatékony polinomidő közelítési sémát vagy egy hatékony polinomiális idő közelítési sémát ( EPTAS ), amelynél a futási időnek O ( n c ) kell lennie, ahol a c konstans független ε-től. Ez biztosítja, hogy a bemeneti adatok méretének növelése ε értékétől függetlenül növelje a végrehajtási időt; az O jel alatti tényező azonban továbbra is tetszőlegesen ε-tól függ. További, a gyakorlatban hasznosabb megszorítás a teljesen polinomiális idejű közelítési séma ( FPTAS ), amely megköveteli, hogy az algoritmus futási ideje polinomiálisan függjön mind az n , mind az 1/ε probléma méretétől. Példa egy olyan problémára, amelyre az FPTAS létezik, a hátizsák-probléma . De még PTAS sem létezik a kapcsolódó konténerezési problémára .

Bármely erősen NP-nehéz optimalizálási probléma polinomiálisan korlátos célfüggvénnyel nem rendelkezhet FPTAS-val. [2] Ennek ellenkezője azonban nem igaz. A 2D hátizsák probléma nem erősen NP-nehéz, de nincs FPTAS még akkor sem, ha a célfüggvény polinomiálisan korlátos. [3]

FPTAS futtatása ⊊ PTAS ⊊  APX . Ezért az APX-kemény problémák nem rendelkeznek PTAS-val.

A PTAS másik módosítása a kvázi-polinom-idő közelítési séma ( QPTAS ) . A QPTAS időbeli összetettséggel rendelkezik minden rögzített esetén .

Véletlenszerű algoritmusok

Egyes problémák, amelyek nem rendelkeznek PTAS - val, hasonló tulajdonságokkal rendelkező véletlenszerű algoritmusokkal rendelkezhetnek - polinom-idő randomizált közelítési séma vagy polinom-idő véletlenszerű közelítési séma ( PRAS ). A PRAS algoritmus ε > 0 paraméterrel az optimalizálási feladat tetszőleges adathalmazára olyan megoldást talál polinom időben, amely nem haladja meg (1 + ε)OPT nagy valószínűséggel. A "nagy valószínűség" általában 3/4-nél nagyobb valószínűséget jelent, bár a definíció nem adja meg ezt az értéket. A PTAS algoritmushoz hasonlóan a PRAS algoritmusnak is rendelkeznie kell olyan futási idővel, amely polinomiálisan függ n -től , de nem 1/ε-tól. A determinisztikus algoritmusokhoz hasonlóan bevezetik az EPTAS -hoz hasonló EPRAS-t és az FPTAS - hoz hasonló FPRAS-t. [2]

Jegyzetek

  1. ↑ Sanjeev Arora , Polinomidő közelítési sémák euklideszi TSP-hez és más geometriai problémákhoz, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 2 Vazirani, Vijay V. Közelítő algoritmusok  (határozatlan) . - Berlin: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer és U. Pferschy és D. Pisinger. Hátizsákproblémák  (neopr.) . — Springer, 2004.

Linkek