Ungefärligt polynomtidsschema

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 april 2022; kontroller kräver 2 redigeringar .

I matematik betecknar polynom- tidsapproximationsschema eller polynom- tidsapproximationsschema ( PTAS ) en klass av approximativa polynom-tidsalgoritmer för att lösa generellt NP-hårda optimeringsproblem. Om P = NP, förlorar introduktionen av detta begrepp sin mening. Därför kommer vi vidare att anta att Р inte sammanfaller med NP. Och utan förlust av generalitet definierar vi konceptet för minimeringsproblemet.

Definition

PTAS är en familj av algoritmer beroende på parametern ε , så att för en godtycklig uppsättning data för något optimeringsproblem och parameter ε > 0, hittar familjens algoritm en lösning i polynomtid med objektivfunktionen S < (1 + ε)OPT, där OPT är minimum av objektivfunktionen. Till exempel, för resandeförsäljarproblemet i det euklidiska rymden, finns det en PTAS som hittar en korsningsväg med längd som mest (1 + ε) L , där L är längden på den kortaste vägen. [ett]

Exekveringstiden för PTAS måste bero polynomiellt på n för alla fasta ε, men kan variera godtyckligt när ε ändras. Algoritmer med körtid O ( n 1/ε ) eller till och med O ( n exp(1/ε) ) är PTAS-algoritmer.

Deterministiska algoritmer

I PTAS-algoritmer kan exponenten i komplexitetsuppskattning växa katastrofalt när ε minskar, till exempel när exekveringstiden är O( n (1/ε)! ), vilket gör denna klass av algoritmer av lite intresse ur praktisk synvinkel . Man kan definiera ett effektivt polynom- tidsapproximationsschema eller ett effektivt polynom- tidsapproximationsschema ( EPTAS ) för vilket körtiden måste vara O ( nc ), där konstanten c är oberoende av ε. Detta säkerställer att en ökning av storleken på indata ökar exekveringstiden, oavsett värdet på ε; faktorn under O -tecknet fortsätter dock att vara godtyckligt beroende av ε. En ytterligare restriktion som är mer användbar i praktiken är det fullständiga polynom- tidsapproximationsschemat ( FPTAS ), som kräver att algoritmens körtid beror polynomiellt på både problemstorleken n och 1/ε. Ett exempel på ett problem för vilket FPTAS finns är ryggsäcksproblemet . Men det finns inte ens en PTAS för det relaterade containeriseringsproblemet .

Alla starkt NP-hårda optimeringsproblem med en polynomiellt bunden objektivfunktion kan inte ha en FPTAS. [2] Det omvända är dock inte sant. 2D-ryggsäcksproblemet är inte starkt NP-hårt, men har ingen FPTAS även när den objektiva funktionen är polynomiellt begränsad. [3]

Kör FPTAS ⊊ PTAS ⊊  APX . Därför har APX-hårda problem inte PTAS.

En annan modifiering av PTAS är quasi -polynomial-time approximation scheme ( QPTAS ) . QPTAS har tidskomplexitet för alla fasta .

Randomiserade algoritmer

Vissa problem som inte har PTAS kan ha randomiserade algoritmer med liknande egenskaper - polynom-time randomized approximation scheme eller polynom-time randomized approximation scheme ( PRAS ). PRAS-algoritmen med parametern ε > 0 för en godtycklig datamängd för optimeringsproblemet finner i polynomtid en lösning som inte överskrider (1 + ε)OPT med hög sannolikhet. Vanligtvis betyder "hög sannolikhet" en sannolikhet som är större än 3/4, även om definitionen inte anger detta värde. Precis som PTAS-algoritmen måste PRAS-algoritmen ha en gångtid som polynomiellt beror på n , men inte på 1/ε. I analogi med deterministiska algoritmer introduceras EPRAS som liknar EPTAS och FPRAS som liknar FPTAS. [2]

Anteckningar

  1. ↑ Sanjeev Arora , Polynomial-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. Approximationsalgoritmer  (obestämd) . - Berlin: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer och U. Pferschy och D. Pisinger. Knapsäcksproblem  (neopr.) . — Springer, 2004.

Länkar