Přibližné polynomiální časové schéma

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. dubna 2022; kontroly vyžadují 2 úpravy .

V matematice , polynomial-časové aproximační schéma nebo polynomial-časové aproximační schéma ( PTAS ) označuje třídu přibližných polynomiálních-časových algoritmů pro řešení obecně NP-tvrdých optimalizačních problémů. Pokud P = NP, pak zavedení tohoto pojmu ztrácí smysl. Proto budeme dále předpokládat, že Р se neshoduje s NP. A bez ztráty obecnosti definujeme koncept pro problém minimalizace.

Definice

PTAS je rodina algoritmů závislých na parametru ε , takže pro libovolnou množinu dat nějakého optimalizačního problému a parametru ε > 0 najde algoritmus rodiny řešení v polynomiálním čase s účelovou funkcí S < (1 + ε)OPT, kde OPT je minimum účelové funkce. Například pro problém cestujícího obchodníka v euklidovském prostoru existuje PTAS, který najde dráhu přejezdu o délce nejvýše (1 + ε) L , kde L je délka nejkratší cesty. [jeden]

Doba provádění PTAS musí záviset polynomiálně na n pro jakékoli pevné ε, ale může se libovolně měnit, jak se ε mění. Algoritmy s dobou běhu O ( n 1/ε ) nebo dokonce O ( n exp(1/ε) ) jsou algoritmy PTAS.

Deterministické algoritmy

V algoritmech PTAS může exponent v odhadu složitosti katastroficky narůst, když se ε snižuje, například když je doba provádění O( n (1/ε)! ), což z praktického hlediska činí tuto třídu algoritmů málo zajímavou. . Lze definovat efektivní polynomiálně-časové aproximační schéma nebo efektivní polynomiálně-časové aproximační schéma ( EPTAS ), pro které musí být doba běhu O ( nc ) , kde konstanta c je nezávislá na ε. To zajišťuje, že zvýšení velikosti vstupních dat prodlužuje dobu provádění bez ohledu na hodnotu ε; faktor pod znaménkem O však nadále závisí libovolně na ε. Dalším omezením, které je v praxi užitečnější, je schéma plně polynomiální aproximace ( FPTAS ), které vyžaduje, aby doba běhu algoritmu závisela polynomiálně jak na velikosti problému n , tak na 1/ε. Příkladem problému, pro který existuje FPTAS, je problém s batohem . Ale neexistuje ani PTAS pro související problém kontejnerizace .

Žádný silně NP-obtížný optimalizační problém s polynomiálně ohraničenou účelovou funkcí nemůže mít FPTAS. [2] Opak však není pravdou. 2D problém batohu není silně NP-obtížný, ale nemá FPTAS, i když je účelová funkce polynomiálně omezená. [3]

Spusťte FPTAS ⊊ PTAS ⊊  APX . Proto problémy APX-hard nemají PTAS.

Další modifikací PTAS je kvazi -polynomiální-časové aproximační schéma ( QPTAS ) . QPTAS má časovou složitost pro jakoukoli pevnou .

Randomizované algoritmy

Některé problémy, které nemají PTAS, mohou mít randomizované algoritmy s podobnými vlastnostmi – polynomiálně-časově randomizované aproximační schéma nebo polynomiálně-časově randomizované aproximační schéma ( PRAS ). Algoritmus PRAS s parametrem ε > 0 pro libovolnou datovou sadu optimalizačního problému najde v polynomiálním čase řešení, které s vysokou pravděpodobností nepřekročí (1 + ε)OPT. Typicky "vysoká pravděpodobnost" znamená pravděpodobnost větší než 3/4, ačkoli definice tuto hodnotu nespecifikuje. Stejně jako algoritmus PTAS musí mít algoritmus PRAS dobu běhu, která závisí polynomiálně na n , ale ne na 1/ε. Analogicky s deterministickými algoritmy jsou zavedeny EPRAS podobné EPTAS a FPRAS podobné FPTAS. [2]

Poznámky

  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. Aproximační algoritmy  (neurčité) . - Berlín: Springer, 2003. - S.  294 -295. — ISBN 3-540-65367-8 .
  3. ↑ H. Kellerer a U. Pferschy a D. Pisinger. Problémy  s batohem (neopr.) . - Springer, 2004.

Odkazy