Tilnærmet polynomisk tidsskema

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. april 2022; checks kræver 2 redigeringer .

I matematik betegner polynomial- tidstilnærmelsesskema eller polynomial- tidstilnærmelsesskema ( PTAS ) en klasse af tilnærmede polynomiale- tidsalgoritmer til løsning af generelt NP-hårde optimeringsproblemer. Hvis P = NP, så mister introduktionen af ​​dette begreb sin betydning. Derfor vil vi yderligere antage, at Р ikke falder sammen med NP. Og uden tab af generalitet definerer vi konceptet for minimeringsproblemet.

Definition

PTAS er en familie af algoritmer afhængig af parameteren ε, således at for et vilkårligt sæt af data for et eller andet optimeringsproblem og parameter ε > 0, finder familiens algoritme en løsning i polynomisk tid med den objektive funktion S < (1 + ε)OPT, hvor OPT er minimum af den objektive funktion. For eksempel, for det rejsende sælgerproblem i det euklidiske rum, er der en PTAS, der finder en gennemløbsvej af længden på højst (1 + ε) L , hvor L er længden af ​​den korteste vej. [en]

Udførelsestiden for PTAS skal polynomielt afhænge af n for enhver fast ε, men kan variere vilkårligt, når ε ændres. Algoritmer med køretid O ( n 1/ε ) eller endda O ( n exp(1/ε) ) er PTAS-algoritmer.

Deterministiske algoritmer

I PTAS-algoritmer kan eksponenten i kompleksitetsestimering vokse katastrofalt, efterhånden som ε falder, for eksempel når eksekveringstiden er O( n (1/ε)! ), hvilket gør denne klasse af algoritmer af ringe interesse fra et praktisk synspunkt. . Man kan definere et effektivt polynomium-tidstilnærmelsesskema eller et effektivt polynomium- tidstilnærmelsesskema ( EPTAS ), hvor køretiden skal være O ( n c ), hvor konstanten c er uafhængig af ε. Dette sikrer, at forøgelse af størrelsen af ​​inputdataene øger eksekveringstiden, uanset værdien af ​​ε; faktoren under O- tegnet er dog fortsat vilkårligt afhængig af ε. En yderligere begrænsning, der er mere anvendelig i praksis, er FPTAS ( fuldt polynomial-time approksimation scheme ) , som kræver, at algoritmens køretid afhænger polynomielt af både problemstørrelsen n og 1/ε. Et eksempel på et problem, som FPTAS eksisterer for, er rygsækproblemet . Men der er ikke engang en PTAS for det relaterede containeriseringsproblem .

Ethvert stærkt NP-hårdt optimeringsproblem med en polynomisk afgrænset objektivfunktion kan ikke have en FPTAS. [2] Det modsatte er dog ikke sandt. 2D rygsækproblemet er ikke stærkt NP-hårdt, men har ingen FPTAS, selv når den objektive funktion er polynomielt afgrænset. [3]

Kør FPTAS ⊊ PTAS ⊊  APX . Derfor har APX-hårde problemer ikke PTAS.

En anden modifikation af PTAS er quasi -polynomial-time approksimation scheme ( QPTAS ) . QPTAS har tidskompleksitet for enhver fast .

Randomiserede algoritmer

Nogle problemer, der ikke har PTAS, kan have randomiserede algoritmer med lignende egenskaber - polynomial-time randomized approximation scheme eller polynomial-time randomized approximation scheme ( PRAS ). PRAS-algoritmen med parameteren ε > 0 for et arbitrært datasæt af optimeringsproblemet finder i polynomiel tid en løsning, der ikke overstiger (1 + ε)OPT med høj sandsynlighed. Typisk betyder "høj sandsynlighed" en sandsynlighed større end 3/4, selvom definitionen ikke specificerer denne værdi. Ligesom PTAS-algoritmen skal PRAS-algoritmen have en køretid, der polynomielt afhænger af n , men ikke af 1/ε. Analogt med deterministiske algoritmer introduceres EPRAS svarende til EPTAS og FPRAS svarende til FPTAS. [2]

Noter

  1. ↑ Sanjeev Arora , Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problemer, Journal of the ACM 45(5) 753–782, 1998.
  2. ↑ 1 2 Vazirani, Vijay V. Approximationsalgoritmer  (ubestemt) . - Berlin: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer og U. Pferschy og D. Pisinger. Rygsækproblemer  (neopr.) . - Springer, 2004.

Links