Redukcja zachowująca przybliżenie

W teorii obliczalności i teorii złożoności obliczeniowej , zwłaszcza w badaniu algorytmów aproksymacyjnych , redukcja zachowująca przybliżenie to algorytm przekształcania jednego problemu optymalizacyjnego w inny problem, tak że odległość rozwiązań od optymalnych jest do pewnego stopnia zachowana. Redukcje zachowujące przybliżenie są podzbiorem bardziej ogólnych redukcji w teorii złożoności; różnica polega na tym, że redukcje zachowujące aproksymację zwykle formułują stwierdzenia dotyczące problemów aproksymacji lub problemów optymalizacyjnych , w przeciwieństwie do problemów decyzyjnych .

Intuicyjnie problem A można zredukować do problemu B poprzez redukcję zachowującą przybliżenie, jeśli mając przypadek problemu A i (prawdopodobnie przybliżone) rozwiązanie problemu B, można przekształcić przypadek problemu A w przypadek problemu B, zastosować rozwiązania problemu B i odzyskać rozwiązanie problemu A, które również ma pewną gwarancję przybliżenia.

Definicja

W przeciwieństwie do redukcji problemów decyzyjnych, redukcja zachowująca aproksymację musi zachować więcej niż prawdziwość przypadków problemu podczas redukowania od jednego problemu do drugiego. Musi również zachować pewną gwarancję relacji między kosztem rozwiązania a kosztem optimum w obu problemach. Aby sformalizować:

Niech $A$ i $B$ będą problemami optymalizacyjnymi.

Niech $x$ będzie przykładem problemu $A$ z optymalnym rozwiązaniem ${\ displaystyle {\ text {OPT}} (x)}$ . Niech oznacza koszt rozwiązania $y$ dla instancji $x$ problemu $A do$ $)}$ . Jest to również miara używana do określenia, które rozwiązanie jest uważane za optymalne.

Redukcja zachowująca przybliżenie to para funkcji (które często muszą być obliczalne w czasie wielomianowym), takie że: ${\ displaystyle (f, g) }$

$f$ odwzorowuje instancję $x$ A na instancję B $_$ $_$ $_$ _
$g$ odwzorowuje rozwiązanie $_$ na rozwiązanie A . _ $_$ $_$ $_$
$g zachowuje pewną gwarancję$ wydajności , rozwiązania czyli współczynnik aproksymacji , zdefiniowany jako ${\ Displaystyle R_ {A} (x, y) = \ max \ lewo ({\ Frac {c_ {A} (x, {\ tekst {OPT}} (x) )}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,{\text{OPT}}(x))}} \prawo)}$ .

typy

Istnieje wiele różnych rodzajów redukcji zachowujących aproksymację, z których każda ma inną gwarancję (trzeci punkt w powyższej definicji). Jednak w przeciwieństwie do innych redukcji, redukcje zachowujące aproksymację często nakładają się na siebie pod względem właściwości, które wykazują w problemach optymalizacyjnych (np. przynależność do klasy złożoności lub kompletność lub nieprzybliżalność). Zamiast tego stosuje się różne rodzaje redukcji jako różne techniki redukcji, w których stosuje się odpowiednią redukcję, która jest najłatwiejsza do dostosowania do problemu.

Nie wszystkie rodzaje redukcji zachowujących aproksymację można wykorzystać do pokazania przynależności do wszystkich klas złożoności aproksymacji, z których najbardziej godnymi uwagi są PTAS i APX . Poniższa redukcja zachowuje członkostwo w klasie złożoności C, jeśli biorąc pod uwagę problem A, który redukuje się do problemu B za pomocą schematu redukcji, a B jest w C, to A jest również w C. Niektóre redukcje pokazane poniżej zachowują tylko członkostwo w APX lub PTAS, ale nie inne. Z tego powodu należy dokonać starannego wyboru przy wyborze redukcji zachowujących przybliżenie, zwłaszcza w celu udowodnienia kompletności problemu w ramach klasy złożoności.

Crescenzi sugeruje, że trzema najbardziej idealnymi stylami redukcji, zarówno pod względem łatwości użycia, jak i siły udowodnienia, są redukcja PTAS, redukcja AP i redukcja L. Poniższe opisy redukcji pochodzą z ankiety Crescenziego dotyczącej redukcji zachowujących przybliżenie.

Ścisła redukcja

Ścisła redukcja jest najprostszym rodzajem redukcji zachowującej przybliżenie. W ścisłej redukcji stosunek aproksymacji rozwiązania y' do przypadku x' problemu B musi być co najwyżej tak dobry, jak stosunek aproksymacji odpowiedniego rozwiązania y do przypadku x problemu A. Innymi słowy:

{\ Displaystyle R_ {A} (x, y) \ równoważnik R_ {B} (x', y')}

dla

{\ Displaystyle x '= f (x), y = g (y')}

.

Ścisła redukcja jest najprostsza: jeśli istnieje ścisła redukcja od problemu A do problemu B, to problem A zawsze można przybliżyć do co najmniej tak dobrego stosunku jak problem B. Ścisła redukcja zachowuje członkostwo zarówno w PTAS, jak i APX.

Istnieje podobna koncepcja redukcji S, dla której $\ Displaystyle c_ {A} (x, y) = c_ {B} (x' ,y')}$ , a optyma dwóch odpowiednich instancji również muszą mieć ten sam koszt. S-redukcja jest bardzo szczególnym przypadkiem ścisłej redukcji i jest jeszcze bardziej ograniczająca. W efekcie dwa problemy A i B muszą być ze sobą niemal idealnie zgodne. Istnienie redukcji S implikuje istnienie nie tylko ścisłej redukcji, ale każdej innej wymienionej tutaj redukcji.

redukcja L

L-redukcje zachowują członkostwo zarówno w PTAS, jak i APX (ale tylko dla problemów minimalizacji w przypadku tych ostatnich ). W rezultacie nie mogą być ogólnie używane do udowodnienia kompletności wyników dotyczących APX, Log-APX lub Poly-APX, niemniej jednak są cenione za naturalną formułę i łatwość użycia w dowodach.

Redukcja PTAS

Redukcja PTAS to kolejny powszechnie stosowany schemat redukcji. Chociaż zachowuje członkostwo w PTAS, nie robi tego w przypadku APX. Niemniej jednak kompletność APX jest definiowana w kategoriach redukcji PTAS.

Redukcje PTAS są uogólnieniem redukcji P, pokazanych poniżej, z tą różnicą, że funkcja $g$ może zależeć od współczynnika aproksymacji $r$ .

Redukcja A i Redukcja P

Redukcja A i redukcja P to podobne schematy redukcji, które można wykorzystać do pokazania przynależności odpowiednio do APX i PTAS. Obie wprowadzają nową funkcję $c$ , zdefiniowaną na liczbach większych niż 1, które muszą być obliczalne.

W redukcji A mamy to

{\ Displaystyle R_ {B} (x', y') \ równoważnik r \ strzałka w prawo R_ {A} (x, y)\równoważnik c(r)}

.

W redukcji P mamy to

{\ Displaystyle R_ {B} (x', y') \ równoważnik c (r) \ strzałka w prawo R_ {A} (x,y)\równik r}

.

Istnienie redukcji P implikuje istnienie redukcji PTAS.

E-redukcja

E-redukcja, która jest uogólnieniem ścisłej redukcji, ale implikuje zarówno redukcję A, jak i redukcję P, jest przykładem mniej restrykcyjnego stylu redukcji, który zachowuje przynależność nie tylko do PTAS i APX, ale także do większych klas Log- APX i Poli-APX . $E$ -redukcja wprowadza dwa nowe parametry, wielomian $p$ i . Jego definicja jest następująca.

$stałej$ redukcji mamy to dla pewnego wielomianu $p$ i ,

$\ Displaystyle c_ {B} ({\ tekst {OPCJA}} _ {B} (x ')) \leq p(|x|)c_{A}({\text{OPT}}_{A}(x))}$ , gdzie ${\ displaystyle | x|}$ oznacza rozmiar opisu instancji problemu.
$($ ZA ${A$ + x $'$ .

Aby uzyskać redukcję A z redukcji E, niech do ${\ Displaystyle c (r) = 1 + \ beta \ cdot (r-1)$ uzyskać redukcję P z redukcji E, niech do $= 1 + (r-1) / \ beta}$ .

Redukcja AP

Redukcje AP służą do definiowania kompletności w klasach Log-APX i Poly-APX . Stanowią szczególny przypadek redukcji PTAS, spełniając następujące ograniczenia.

W redukcji AP mamy to dla pewnej stałej , ${\ displaystyle \ alpha$ }

{\ Displaystyle R_ {B} (x', y') \ równoważnik r \ rightarrow R_ { A}(x,y)\leq 1+\alpha \cdot (r-1)}

z dodatkowym uogólnieniem, że funkcja $g$ może zależeć od współczynnika aproksymacji $r$ , jak w redukcji PTAS.

Redukcja AP jest również uogólnieniem redukcji E. W rzeczywistości należy nałożyć dodatkowe ograniczenie na redukcję AP, aby zachować członkostwo Log-APX i Poly-APX, tak jak ma to miejsce w przypadku redukcji E: dla ustalonego rozmiaru problemu czas obliczeń $f, g$ musi nie rosnąć, ponieważ współczynnik aproksymacji wzrasta.

Redukcja luki

Redukcja luki jest rodzajem redukcji, która, choć przydatna do udowodnienia pewnych wyników nieprzybliżenia, nie przypomina innych przedstawionych tutaj redukcji. Redukcja luk zajmuje się problemami optymalizacyjnymi w ramach kontenera problemu decyzyjnego, generowanego przez zmianę celu problemu na rozróżnienie między rozwiązaniem optymalnym a rozwiązaniami o pewien czynnik mnożnikowy gorszy od optymalnego.

Zobacz też