Schemat aproksymacji w czasie wielomianowym

W informatyce (zwłaszcza algorytmice ) schemat aproksymacji w czasie wielomianowym ( PTAS ) jest rodzajem algorytmu aproksymacji problemów optymalizacyjnych (najczęściej NP-trudnych problemów optymalizacyjnych).

PTAS to algorytm, który bierze przykład problemu optymalizacyjnego i parametr $ε > 0$ i tworzy rozwiązanie, które mieści się w zakresie współczynnika $1 + ε$ od bycia optymalnym (lub $1 - ε$ w przypadku problemów maksymalizacji). Na przykład dla problemu euklidesowego komiwojażera PTAS wytworzyłby trasę o długości co najwyżej $(1 + ε) L$ , gdzie $L$ jest długością najkrótszej trasy.

Czas działania PTAS musi być wielomianem wielkości problemu dla każdego ustalonego ε, ale może być różny dla różnych ε. Zatem algorytm działający w czasie $O (n 1/ε)$ lub nawet $O (n exp(1/ε))$ liczy się jako PTAS.

Warianty

deterministyczny

Praktyczny problem z algorytmami PTAS polega na tym, że wykładnik wielomianu może dramatycznie rosnąć wraz ze zmniejszaniem się ε, na przykład jeśli czas działania wynosi $O (n (1/ε)!)$ . Jednym ze sposobów rozwiązania tego problemu jest zdefiniowanie wydajnego schematu aproksymacji czasu wielomianowego lub EPTAS , w którym czas działania musi wynosić $O (n c)$ dla stałej $c$ niezależnej od $ε$ . Zapewnia to, że wzrost rozmiaru problemu ma taki sam względny wpływ na czas wykonywania, niezależnie od używanego ε; jednak stała pod dużym O może nadal arbitralnie zależeć od ε. Innymi słowy, EPTAS działa w FPT , gdzie parametrem jest ε.

Jeszcze bardziej restrykcyjny i użyteczny w praktyce jest w pełni wielomianowy schemat aproksymacji czasu lub FPTAS , który wymaga, aby algorytm był wielomianem zarówno w rozmiarze problemu $n$ , jak i $1/ε$ .

Jeśli P = NP , oznacza to , że FPTAS ⊊ PTAS ⊊ APX . W konsekwencji, przy tym założeniu, problemy APX-hard nie mają PTAS.

Innym deterministycznym wariantem PTAS jest schemat aproksymacji czasu quasi-wielomianowego lub QPTAS . QPTAS ma złożoność czasową $n polylog (n)$ dla każdego ustalonego $ε > 0$ . Ponadto PTAS może działać w FPT dla pewnej parametryzacji problemu, co prowadzi do sparametryzowanego schematu aproksymacji .

Randomizowane

Niektóre problemy, które nie mają PTAS, mogą dopuszczać losowy algorytm o podobnych właściwościach, schemat aproksymacji z randomizacją w czasie wielomianowym lub PRAS . PRAS to algorytm, który bierze przykład problemu optymalizacji lub liczenia i parametru $ε > 0$ i w czasie wielomianowym tworzy rozwiązanie, które z dużym prawdopodobieństwem mieści się w granicach współczynnika $ε$ optymalnego. Konwencjonalnie „wysokie prawdopodobieństwo” oznacza prawdopodobieństwo większe niż 3/4, chociaż podobnie jak w przypadku większości probabilistycznych klas złożoności definicja jest odporna na zmiany tej dokładnej wartości (wymagane minimum jest na ogół większe niż 1/2). Podobnie jak PTAS, PRAS musi mieć wielomian czasu działania w $n$ , ale niekoniecznie w $ε$ ; z dalszymi ograniczeniami dotyczącymi czasu działania w $ε$ , można zdefiniować wydajny schemat aproksymacji z randomizacją w czasie wielomianowym lub EPRAS podobny do EPTAS, oraz w pełni wielomianowy schemat aproksymacji z randomizacją lub FPRAS podobny do FPTAS.

Jako klasa złożoności

Termin PTAS może być również używany w odniesieniu do klasy problemów optymalizacyjnych, które mają PTAS. PTAS jest podzbiorem APX i jeśli P = NP , jest podzbiorem ścisłym.

Członkostwo w PTAS można wykazać za pomocą redukcji PTAS , redukcji L lub redukcji P , z których wszystkie zachowują członkostwo w PTAS, i można je również wykorzystać do wykazania kompletności PTAS. Z drugiej strony wykazanie braku członkostwa w PTAS (mianowicie nieistnienia PTAS) można zrobić, pokazując, że problem jest APX-trudny, po czym istnienie PTAS pokazałoby P = NP. Twardość APX jest zwykle pokazywana poprzez redukcję PTAS lub redukcję AP .

Zobacz też

Sparametryzowany schemat aproksymacji , schemat aproksymacji działający w czasie FPT

^ Sanjeev Arora , schematy aproksymacji czasu wielomianowego dla euklidesowego TSP i innych problemów geometrycznych, Journal of the ACM 45 (5) 753–782, 1998.
^ ^ab ^.; Jansen, Thomas (1998), „Wprowadzenie do teorii złożoności i algorytmów aproksymacji”, w: Mayr, Ernst W Prömel, Hans Jürgen; Steger, Angelika (red.), Wykłady z weryfikacji dowodu i algorytmów aproksymacji , Springer, s. 5–28, doi : 10.1007 / BFb0053011 , ISBN 9783540642015 . Patrz omówienie następujące po Definicji 1.30 na s. 20 .
^ Vazirani, Vijay V. (2003). Algorytmy aproksymacji . Berlin: Springer. s. 294–295. ISBN 3-540-65367-8 .

Linki zewnętrzne

Zoo złożoności: PTAS , EPTAS .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpiński i Gerhard Woeginger , Kompendium problemów optymalizacji NP – wymień, które problemy optymalizacji NP mają PTAS.

[1] Sanjeev Arora , schematy aproksymacji czasu wielomianowego dla euklidesowego TSP i innych problemów geometrycznych, Journal of the ACM 45 (5) 753–782, 1998.

[Jansen-2] .; Jansen, Thomas (1998), „Wprowadzenie do teorii złożoności i algorytmów aproksymacji”, w: Mayr, Ernst W Prömel, Hans Jürgen; Steger, Angelika (red.), Wykłady z weryfikacji dowodu i algorytmów aproksymacji , Springer, s. 5–28, doi : 10.1007 / BFb0053011 , ISBN 9783540642015 . Patrz omówienie następujące po Definicji 1.30 na s. 20 .

[vvv-3] Vazirani, Vijay V. (2003). Algorytmy aproksymacji . Berlin: Springer. s. 294–295. ISBN 3-540-65367-8 .