Schéma aproximace v polynomiálním čase - Polynomial-time approximation scheme

v počítačová věda, a schéma polynomiálního času (PTAS) je typ aproximační algoritmus pro optimalizační problémy (nejčastěji, NP-tvrdé optimalizační problémy).

PTAS je algoritmus, který přebírá instanci problému s optimalizací a parametr ε> 0 a v polynomiálním čase vytváří řešení, které je v rámci faktoru 1 + ε optimálního (nebo 1 - ε pro problémy s maximalizací). Například pro euklidovce problém obchodního cestujícího, PTAS by vytvořil turné s maximální délkou (1 + ε)L, s L což je délka nejkratší cesty.[1] Existuje také PTAS pro třídu všech problémů s uspokojením hustých omezení (CSP).[2][je zapotřebí objasnění ]

Je nutné, aby doba provozu PTAS byla polynomiální n pro každé pevné ε, ale může se lišit pro různé ε. Algoritmus tedy běží v čase Ó (n1 / ε) nebo dokonce Ó(nexp (1 / ε)) se počítá jako PTAS.

Varianty

Deterministický

Praktickým problémem s algoritmy PTAS je, že exponent polynomu by se mohl dramaticky zvětšit, jak se zmenší ε, například pokud je runtime O (n(1 / ε)!). Jedním ze způsobů, jak to vyřešit, je definovat efektivní schéma aproximace v polynomiálním čase nebo EPTAS, ve kterém je požadována doba provozu Ó(nC) pro konstantu C nezávisle na ε. Tím je zajištěno, že zvětšení velikosti problému má stejný relativní účinek na běh bez ohledu na to, jaké ε se používá; konstanta pod velký-O může stále záviset na ε libovolně. Ještě více omezující a v praxi užitečné je schéma plně polynomiálního času nebo FPTAS, což vyžaduje, aby byl algoritmus polynomiální ve velikosti problému n a 1 / ε. Všechny problémy v FPTAS jsou fixovatelný parametr s ohledem na standardní parametrizaci. Oba batoh problém a problém s balením koše přiznat FPTAS.[3]

Žádný silně NP-tvrdé optimalizační problém s polynomiálně ohraničenou objektivní funkcí nemůže mít FPTAS, pokud P = NP.[4] Konverzace však selže: např. pokud P se nerovná NP, batoh se dvěma omezeními není silně NP-tvrdý, ale nemá FPTAS, i když je optimální cíl polynomiálně ohraničený.[5]

Ledaže P = NP, platí, že FPTAS ⊊ PTAS ⊊APX.[6] V důsledku toho za tohoto předpokladu APX-hard problémy nemají PTAS.

Další deterministickou variantou PTAS je schéma kvazi-polynomiálního času nebo QPTAS. QPTAS má časovou složitost pro každou pevnou .

Náhodně

Některé problémy, které nemají PTAS, mohou připustit a randomizovaný algoritmus s podobnými vlastnostmi, a schéma randomizovaného přiblížení v polynomiálním čase nebo PRAS. PRAS je algoritmus, který přebírá instanci problému s optimalizací nebo počítáním a parametr ε> 0 a v polynomiálním čase vytváří řešení, které má vysoká pravděpodobnost být uvnitř faktoru ε optimálního. Konvenčně „vysoká pravděpodobnost“ znamená pravděpodobnost větší než 3/4, ačkoli jako u většiny pravděpodobnostních tříd složitosti je definice robustní vůči odchylkám v této přesné hodnotě (minimální minimální požadavek je obecně větší než 1/2). Stejně jako PTAS musí mít PRAS polynom v době běhu n, ale ne nutně v ε; s dalšími omezeními doby provozu v ε lze definovat efektivní randomizované aproximační schéma v polynomiálním čase nebo EPRAS podobné EPTAS a plně randomizované aproximační schéma v polynomiálním čase nebo FPRAS podobný FPTAS.[4]

Jako třída složitosti

Termín PTAS lze také použít k označení třídy optimalizačních problémů, které mají PTAS. PTAS je podmnožina APX, a pokud P = NP, je to přísná podmnožina. [6]

Členství v PTAS lze zobrazit pomocí a Snížení PTAS, L-redukce nebo P-redukce, které všechny zachovávají členství v PTAS, a ty lze také použít k prokázání úplnosti PTAS. Na druhou stranu, ukázání nečlenství v PTAS (jmenovitě neexistence PTAS), může být provedeno ukázáním, že problém je tvrdý APX, po kterém by existence PTAS ukázala P = NP. Tvrdost APX se běžně projevuje redukcí PTAS nebo AP-redukce.

Reference

  1. ^ Sanjeev Arora, Schémata aproximace polynomiálního času pro euklidovskou TSP a další geometrické problémy, Journal of ACM 45 (5) 753–782, 1998.
  2. ^ Arora, S .; Karger, D .; Karpinski, M. (1999), „Schémata polynomiálního přibližování času pro husté případy NP-těžkých problémů“, Journal of Computer and System Sciences, 58 (1): 193–210, doi:10.1006 / jcss.1998.1605
  3. ^ Vazirani, Vijay (2001). Aproximační algoritmy. Berlín: Springer. str.74 –83. ISBN  3540653678. OCLC  47097680.
  4. ^ A b Vazirani, Vijay V. (2003). Aproximační algoritmy. Berlín: Springer. 294–295. ISBN  3-540-65367-8.
  5. ^ H. Kellerer a U. Pferschy a D. Pisinger (2004). Problémy s batohem. Springer.CS1 maint: používá parametr autoři (odkaz)
  6. ^ A b Jansen, Thomas (1998), „Úvod do teorie složitosti a aproximačních algoritmů“, Mayr, Ernst W .; Prömel, Hans Jürgen; Steger, Angelika (eds.), Přednášky o ověřování důkazů a aproximačních algoritmech, Springer, str. 5–28, doi:10.1007 / BFb0053011, ISBN  9783540642015. Viz diskuse následující po definici 1.30 str. 20.

externí odkazy