Schema de timp polinomială aproximativă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 12 aprilie 2022; verificările necesită 2 modificări .

În matematică , schema de aproximare în timp polinomial sau schema de aproximare în timp polinomial ( PTAS ) denotă o clasă de algoritmi aproximativi în timp polinomial pentru rezolvarea problemelor de optimizare în general NP-hard . Dacă P = NP, atunci introducerea acestui concept își pierde sensul. Prin urmare, vom presupune în continuare că Р nu coincide cu NP. Și fără pierderea generalității, definim conceptul pentru problema minimizării.

Definiție

PTAS este o familie de algoritmi în funcție de parametrul ε , astfel încât pentru un set arbitrar de date a unei probleme de optimizare și parametru ε > 0, algoritmul familiei găsește o soluție în timp polinomial cu funcția obiectiv S < (1 + ε)OPT, unde OPT este minimul funcției obiectiv. De exemplu, pentru problema vânzătorului călător în spațiul euclidian, există un PTAS care găsește o cale de traversare cu lungimea de cel mult (1 + ε) L , unde L este lungimea drumului cel mai scurt. [unu]

Timpul de execuție al PTAS trebuie să depindă polinomial de n pentru orice ε fix, dar poate varia în mod arbitrar pe măsură ce ε se modifică. Algoritmii cu timp de rulare O ( n 1/ε ) sau chiar O ( n exp(1/ε) ) sunt algoritmi PTAS.

Algoritmi determiniști

În algoritmii PTAS, exponentul în estimarea complexității poate crește catastrofal pe măsură ce ε scade, de exemplu, când timpul de execuție este O( n (1/ε)! ), ceea ce face ca această clasă de algoritmi să fie puțin interesantă din punct de vedere practic. . Se poate defini o schemă eficientă de aproximare polinomială în timp sau o schemă eficientă de aproximare polinomială în timp ( EPTAS ) pentru care timpul de rulare trebuie să fie O ( n c ), unde constanta c este independentă de ε. Acest lucru asigură că mărirea dimensiunii datelor de intrare crește timpul de execuție, indiferent de valoarea lui ε; cu toate acestea, factorul sub semnul O continuă să depindă în mod arbitrar de ε. O altă constrângere mai utilă în practică este schema de aproximare în timp complet polinomial ( FPTAS ), care necesită ca timpul de rulare al algoritmului să depindă polinomial atât de dimensiunea problemei n , cât și de 1/ε. Un exemplu de problemă pentru care există FPTAS este problema rucsacului . Dar nu există nici măcar un PTAS pentru problema de containerizare aferentă .

Orice problemă de optimizare puternic NP-hard cu o funcție obiectiv mărginită polinomial nu poate avea un FPTAS. [2] Cu toate acestea, inversul nu este adevărat. Problema rucsacului 2D nu este puternic NP-hard, dar nu are FPTAS chiar și atunci când funcția obiectiv este mărginită polinomial. [3]

Rulați FPTAS ⊊ PTAS ⊊  APX . Prin urmare, problemele APX-hard nu au PTAS.

O altă modificare a PTAS este schema de aproximare cvasi-polinomială în timp ( QPTAS ) . QPTAS are complexitate de timp pentru orice fix .

Algoritmi randomizati

Unele probleme care nu au PTAS pot avea algoritmi randomizati cu proprietăți similare - schema de aproximare randomizată în timp polinomial sau schema de aproximare randomizată în timp polinomial ( PRAS ). Algoritmul PRAS cu parametrul ε > 0 pentru un set de date arbitrar al problemei de optimizare găsește în timp polinomial o soluție care nu depășește (1 + ε)OPT cu mare probabilitate. De obicei, „probabilitate mare” înseamnă o probabilitate mai mare de 3/4, deși definiția nu specifică această valoare. Ca și algoritmul PTAS, algoritmul PRAS trebuie să aibă un timp de rulare care depinde polinom de n , dar nu de 1/ε. Prin analogie cu algoritmii determiniști, sunt introduse EPRAS similare cu EPTAS și FPRAS similare cu FPTAS. [2]

Note

  1. ^ Sanjeev Arora , Polinomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 2 Vazirani, Vijay V. Algoritmi de aproximare  (nedefinite) . - Berlin: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer și U. Pferschy și D. Pisinger. Probleme la rucsac  (neopr.) . — Springer, 2004.

Link -uri