Dlaczego wszystkie problemy w FPTAS występują również w FPT?

Zgodnie z artykułem Wikipedii na temat schematów aproksymacji czasu wielomianowego :

Wszystkie problemy w FPTAS są możliwe do rozwiązania ze stałymi parametrami.

Ten wynik mnie zaskakuje - te klasy wydają się zupełnie różne od siebie. FPTAS charakteryzuje problemy na podstawie ich łatwości do przybliżenia, podczas gdy FPT charakteryzuje problemy na podstawie ich trudności w odniesieniu do niektórych parametrów. Niestety Wikipedia (w chwili, gdy zadaję to pytanie) nie podaje na to cytatu.

Czy istnieje standardowy dowód tego wyniku? A może jest jakieś źródło, z którym mogę się dowiedzieć, aby dowiedzieć się więcej o tym połączeniu?

— templatetypedef
źródło

Jest to twierdzenie Cai i Chena (JCSS97), stwierdzające, że „ jeśli problem optymalizacji NP ma w pełni wielomianowy schemat aproksymacji, to jest możliwy do ustalenia z parametrami stałymi ” . Zobacz artykuł na temat ciągalności i przybliżalności optymalizacji NP problemy .

— Pål GD

I oczywiście jako następstwo otrzymujesz „ Problemy optymalizacji NP, które są twarde pod jednolitą redukcją, nie mają schematu aproksymacji w pełni wielomianowej, chyba że $W[1]$ $W[1] = FPT$ .”

— Pål GD

@ PålGD- Chociaż wydaje się, że wybór parametryzacji jest nieco arbitralny; wybierają parametr, który ma być wartością optymalnego rozwiązania dla problemu wejściowego. Przypuszczam, że technicznie to działa, choć intelektualnie niezbyt satysfakcjonujące.

— templatetypedef

Luke Mathieson udzielił bardzo ładnej odpowiedzi poniżej i myślę, że to wystarczy, aby odpowiedzieć na twoje pytanie.

— Pål GD

W rzeczywistości jest silniejszy wynik; Problem występuje w klasie jeśli ma fptas ¹ : aproksymacja działa w czasie ograniczonym przez (tzn. wielomian zarówno pod względem wielkości, jak i współczynnika aproksymacji). Istnieje bardziej ogólna klasa która rozluźnia czas związany z - zasadniczo an podobny do czasu działania w odniesieniu do współczynnika przybliżenia. $\mathrm{FPTAS}$ $\varepsilon$ $(n+\frac{1}{\varepsilon})^{\mathcal{O}(1)}$ $\mathrm{EPTAS}$ $f(\frac{1}{\varepsilon})\cdot n^{\mathcal{O}(1)}$ $\mathrm{FPT}$

Najwyraźniej jest podzbiorem i okazuje się, że jest podzbiorem w następującym znaczeniu: $\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

Twierdzenie Jeśli problem NPO ma $\Pi$ eptas, to sparametryzowane kosztem rozwiązania jest możliwe do ustalenia z parametrami stałymi. $\Pi$

Twierdzenie i dowód podano w Flum & Grohe [1] jako Twierdzenie 1.32 (str. 23-24) i przypisują je Bazganowi [2], co stawia go dwa lata przed słabszym wynikiem Cai & Chena (ale w języku francuskim raport techniczny).

Podam szkic dowodu, ponieważ uważam, że to niezły dowód twierdzenia. Dla uproszczenia zrobię wersję minimalizującą, po prostu mentalnie wykonam odpowiednie inwersje dla maksymalizacji.

Dowód. Niech będzie eptas dla , a następnie możemy zbudować sparametryzowany algorytm dla sparametryzowany kosztem rozwiązania w następujący sposób: biorąc pod uwagę dane wejściowe , uruchamiamy na wejściu gdzie ustawiamy (tzn. wybieramy związany współczynnik przybliżenia ). Niech będzie rozwiązaniem, będzie kosztem a będzie rzeczywistym współczynnikiem przybliżenia do $A$ $\Pi$ $A'$ $\Pi$ $k$ $(x,k)$ $A$ $x$ $\varepsilon := \frac{1}{k+1}$ $1+\frac{1}{k+1}$ $y$ $\text{cost}(x,y)$ $y$ $r(x,y)$ $y$ $\text{opt}(x)$ , tj. . $\text{cost}(x,y) = r(x,y)\cdot \text{opt}(x)$

Jeśli , a następnie zaakceptuj jako . Jeśli , odrzuć jako jako to eptas i $\text{cost}(x,y) \leq k$ $\text{opt}(x) \leq \text{cost}(x,y) \leq k$ $\text{cost}(x,y) > k$ $r(x,y) \leq 1+\frac{1}{k+1}$ $A$

opt (x) = \frac{cost (x, y)}{r (x, y)} \geq \frac{k + 1}{1 + \frac{1}{k + 1}} > k

$\text{opt}(x) = \frac{\text{cost}(x,y)}{r(x,y)} \geq \frac{k+1}{1+\frac{1}{k+1}} > k$

Oczywiście czas związany z biegiem czasu jest określony po prostu z faktu, że jest eptas . $A'$ $A$ $\Box$

Oczywiście, jak zauważa Pål, sparametryzowane wyniki twardości sugerują brak istnienia eptas, chyba że występuje pewne załamanie, ale występują problemy w bez eptas (lub nawet ptas ), więc to ścisły podzbiór (w sensie twierdzenia). $\mathrm{FPT}$ $\mathrm{EPTAS}$ $\mathrm{FPT}$

Przypisy:

An fptas (równoważnie eptas lub PTA ) jest schemat aproksymacji z ograniczonym czasie trwania, jak opisano powyżej. Klasy (równ. , ) jest zbiorem problemów , które mają taki system. $\mathrm{FPTAS}$ $\mathrm{EPTAS}$ $\mathrm{PTAS}$ $\mathrm{NPO}$

[1]: J. Flum i M. Grohe, Parameterized Complexity Theory , Springer, 2006.
[2]: C. Bazgan. Schémas d'approximation et complexité paramétrée , Rapport de DEA, Université Paris Sud, 1995.

— Luke Mathieson
źródło