Schema de aproximare a timpului polinomial

În informatică , o schemă de aproximare în timp polinomial (în engleză polynomial-time approximation scheme sau PTAS) este un tip de algoritm de aproximare pentru probleme de optimizare (foarte des, probleme de optimizare NP-hard ).

Un PTAS este un algoritm care ia o instanță a unei probleme de optimizare și un parametru ε> 0 și, în timp polinomial, produce o soluție care este optimă într-un factor de 1 + ε (sau 1 - ε pentru probleme de maximizare). De exemplu, pentru problema vânzătorului călător euclidian , un PTAS ar produce o circumferință de lungime cel mult (1 + ε) L , L fiind cea mai scurtă lungime a turei. ^[1]

Timpul de execuție al unui PTAS trebuie să fie un timp polinomial în n pentru fiecare ε fix, dar poate fi diferit pentru mai multe εs. Astfel, un algoritm executat în O ( n ^{1 / ε} ) sau, de asemenea, în O ( n ^{exp (1 / ε)} ) contează ca un PTAS.

Variante

Determinat

O problemă practică cu algoritmii PTAS este că exponentul polinomului ar putea crește dramatic atunci când ε se contractă, de exemplu dacă timpul de rulare este O ( n ^{(1 / ε)!} ). O modalitate de a rezolva această problemă este de a defini schema de aproximare eficientă în timp polinomial (în limba engleză „“ sistem de aproximare polinomial de timp eficiente sau EPTAS), în care este necesar ca timpul de execuție este O (n ^c) pentru o constantă c independent de ε. Acest lucru asigură că o creștere a dimensiunii problemei are același efect relativ asupra timpului de funcționare, indiferent de ce ε este utilizat; totuși, constanta sub O-mare poate depinde în mod arbitrar de ε. Chiar mai restrictiv și cel mai util în practică este schema de aproximare în timp complet polinomial ( schema de aproximare în timp complet polinomial sau FPTAS), care impune ca algoritmul să fie un timp polinomial în mărimea n a problemei ca în 1 / ε . Toate problemele din FPTAS pot fi tratate cu parametri fixi . Un exemplu de problemă pe care o are un FPTAS este problema rucsacului .

Orice problemă de optimizare puternic NP-hard cu o funcție obiectiv încadrată polinomial nu poate avea FPTAS decât dacă P = NP. ^[2] Cu toate acestea, inversul nu mai este valabil: de ex. dacă P nu este egal cu NP, rucsacul cu două limite nu este puternic NP-dificil, dar nu are FPTAS chiar și atunci când ținta optimă este delimitată polinomial. ^[3]

Cu excepția cazului în care P = NP , FPTAS ⊊ PTAS ⊊ APX se menține. ^[4] În consecință, conform acestei ipoteze, problemele dificile APX nu au PTAS.

O altă variantă deterministă a PTAS este schema de aproximare în timp cvasi-polinomial (schema de aproximare cvasi-polinomial-timp sau QPTAS). Un QPTAS are complexitate de timp $n^{polylog(n)}$ ${\ displaystyle n ^ {polylog (n)}}$ $n ^ {polylog (n)}$ pentru fiecare $\epsilon >0$ ${\ displaystyle \ epsilon> 0}$ $\ epsilon> 0$ fix.

Randomizat

Unele probleme care nu au PTAS pot permite un algoritm randomizat cu proprietăți similare, o schemă de aproximare randomizată în timp polinomial ( schema de aproximare randomizată în timp polinomial sau PRAS). Un PRAS este un algoritm care ia o instanță a unei probleme de optimizare sau numărare și un parametru ε> 0 și, în timp polinomial, produce o soluție care are o probabilitate ridicată de a se afla într-un factor ε al optimului. În mod convențional, „probabilitate ridicată” înseamnă probabilitate mai mare de 3/4, deși, la fel ca în cazul majorității claselor de complexitate probabilistică, definiția este robustă în ceea ce privește variațiile acestei valori exacte. La fel ca un PTAS, un PRAS trebuie să aibă un timp de rulare polinomial în n , dar nu neapărat în ε; cu restricții suplimentare asupra timpului de execuție în ε, se poate defini o schemă eficientă de aproximare randomizată în timp polinomial ( schemă eficientă de aproximare a timpului polinomial sau EPRAS randomizate ) similare all'EPTAS și una a schemei de aproximare randomizată în timp complet polinomial (complet polinomial -schema de aproximare randomizată în timp sau FPRAS ) similară cu FPTAS. ^[2]

Notă

^ Sanjeev Arora , "Scheme de aproximare în timp polinomial pentru TSP euclidian și alte probleme geometrice", Jurnalul ACM , 45 (5), pp. 753-782, 1998.
^ ^a ^b Vijay V. Vazirani, Algoritmi de aproximare , Berlin, Springer, 2003, pp. 294–295, ISBN 3-540-65367-8 .
^ H. Kellerer, U. Pferschy și D. Pisinger, Knapsack Problems , Springer, 2004.
^ Thomas Jansen, Introducere în teoria algoritmilor de complexitate și de aproximare , în Ernst W. Mayr, Hans Jürgen Prömel și Angelika Steger (ed.), Lectures on Proof Verification and Approximation Algorithms , Springer, 1998, 5-28, DOI : 10.1007 / BFb0053011 , ISBN 9783540642015 . . Vezi discuția care urmează Definiției 1.30 la p. 20 .

linkuri externe

Complexity Zoo : PTAS Arhivat 19 ianuarie 2018 la Internet Archive ., EPTAS Arhivat 27 august 2016 la Internet Archive ., FPTAS Arhivat 27 august 2016 la Internet Archive .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski și Gerhard Woeginger, Un compendiu de probleme de optimizare NP - enumeră probleme de optimizare NP echipate cu PTAS.

Portal IT

Portalul de matematică

[1] Sanjeev Arora , "Scheme de aproximare în timp polinomial pentru TSP euclidian și alte probleme geometrice", Jurnalul ACM , 45 (5), pp. 753-782, 1998.

[vvv-2] Vijay V. Vazirani, Algoritmi de aproximare , Berlin, Springer, 2003, pp. 294–295, ISBN 3-540-65367-8 .

[3] H. Kellerer, U. Pferschy și D. Pisinger, Knapsack Problems , Springer, 2004.

[4] Thomas Jansen, Introducere în teoria algoritmilor de complexitate și de aproximare , în Ernst W. Mayr, Hans Jürgen Prömel și Angelika Steger (ed.), Lectures on Proof Verification and Approximation Algorithms , Springer, 1998, 5-28, DOI : 10.1007 / BFb0053011 , ISBN 9783540642015 . . Vezi discuția care urmează Definiției 1.30 la p. 20 .

[1]

[2]

[3]

[4]