Zależność między stałym parametrem a algorytmem aproksymacyjnym

Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. Przykład . $2^kn^3$

Teraz moje pytanie, czy istnieje górna lub dolna granica wynik w oparciu o relacje między stałym parametrem i zbliżenia zbliża albo zupełnie nie mają żadnego przykładu relationship.For dla problemu mówi się trudne dla niektórych nie ma nic wspólnego z posiadaniem algorytmu aproksymacji c lub PTAS. proszę podać referencje $P$ $W[i]$ $i>0$

cc.complexity-theory reference-request approximation-algorithms fixed-parameter-tractable Prabu
źródło

Powiązane, być może zduplikowane?: Cstheory.stackexchange.com/questions/4906/…

Suresh Venkat

@suresh venkat To pytanie dotyczy różnicy w zrozumieniu NP-zupełnego i ustalonego parametru. kiedy mówimy tylko o twardości NP, wówczas niezależny zbiór i osłona wierzchołków są dosłownie takie same, ale kiedy mówimy w kategoriach stałego parametru, mają one ogromną różnicę. pokrywa wierzchołka ma dobry fpt, podczas gdy niezależny zestaw jest trudny do [1]

Prabu

ale tutaj szukam związku między przybliżeniem a ustalonym parametrem.

Prabu,

Myślę, że nie ma między nimi prawdziwej relacji, ale stosując stały parametr możemy uzyskać dobre przybliżenie, na przykład w pakowaniu bin (harmonogram makespan) można zobaczyć tę relację, lub na przykład na ograniczonych wykresach Treewidth mamy przybliżenia niektórych problemów .

Saeed,

Odpowiedzi:

Istnieje kilka połączeń między sparametryzowanymi algorytmami złożoności i aproksymacji.

Najpierw rozważ tak zwaną standardową parametryzację problemu. Tutaj parametr jest tym, co zoptymalizujesz w wersji optymalizacyjnej problemu (rozmiar pokrywy wierzchołków dla problemu pokrywy wierzchołków, szerokość rozkładu drzewa dla problemu Treewidth itp.). Spójrzmy konkretnie na Vertex Cover. Każde jądro z liniową liczbą wierzchołków dla pokrywy wierzchołków implikuje algorytm aproksymacji czasu wielomianowego o stałym współczynniku: w przybliżonym rozwiązaniu, umieść wszystkie wierzchołki, które zostały wymuszone przez rozwiązanie algorytmu jądra, i wszystkie wierzchołki jądra wystąpienia . Z drugiej strony, dolne granice współczynnika aproksymacji oznaczają niższe granice wielkości jądra. Na przykład w ramach Unique Games Conjecture, Khot i Regev (JCSS 2008)wyklucza algorytmy Przybliżony Vertex przykryć stosunku jakiegokolwiek , która wyklucza jądra dla Vertex Okładka z co najwyżej wierzchołków, , jak również. $c<2$ $ck$ $c<2$

EDYCJA: Argumentacja dla dolnej granicy jądra w poprzednim akapicie jest bardzo nieformalna i, zgodnie z moją najlepszą wiedzą, jest otwarte, czy takie dolne granice wielkości jądra można udowodnić, nawet w przypadku Vertex Cover. Jak wskazuje @Falk w komentarzach, argument dotyczy większości (wszystkich?) Znanych jąder. Nie rozumiem jednak, jak można wykluczyć istnienie algorytmów jądra, w których wykonalne rozwiązanie jądra ma inny współczynnik aproksymacji niż odpowiednie rozwiązanie w wystąpieniu początkowym.

$(1+\epsilon)$ $1/\epsilon$ $\epsilon=1/(k+1)$

$(2^{3k+2}-1)/k$ $g(k)$ $g$ do badania zbliżenia FPT.

Serge Gaspers
źródło

@Gasper Czy widzisz pytanie „Znalezienie maksymalnego acyklicznego sub-turnieju, biorąc pod uwagę dwa acykliczne sub-turnieje”. Nadal mam wątpliwości co do mojej odpowiedzi. Ponieważ pracowałeś z pokrewnym problemem, możesz mi pomóc

Prabu,

Czy pierwszy akapit odpowiedzi Serge'a jest prawidłowy? Czy dolna granica zbliżalności daje dolną granicę wielkości jądra? Podobne stwierdzenie znajduje się w książce Niedermeiera, ale czy to stwierdzenie jest prawidłowe?

XXYYXX,

@XXYYXX: W odpowiedzi Serge'a napisał: „Każde jądro z liniową liczbą wierzchołków dla Cover Vertex implikuje algorytm aproksymacji stałej wielomianowej w czasie” z krótkim dowodem. Dokładniej, jego argument pokazuje, czy istnieje jądro z wierzchołkami ck dla jakiejś stałej c, to istnieje algorytm aproksymacji współczynnika c. Przeciwnie: jeśli nie istnieje algorytm aproksymacji współczynnika c, wówczas nie ma jądra z wierzchołkami ck.

Yoshio Okamoto

@Prabu: Skomentowałem twoją odpowiedź na inne pytanie. @Yoshio: Dziękujemy za odpowiedź na pytanie @ XXYYXX.

Serge Gaspers

W rzeczywistości w przypadku prawdopodobnie wszystkich znanych jąder argument jest podtrzymywany. Nie widzę jednak powodu, dla którego nie powinien istnieć taki, który np. Najpierw redukuje do innego problemu, kernelizuje tam, a następnie redukuje z powrotem do Cover Vertex, tak że powstałe wystąpienie nie ma związku z wierzchołkiem z początkowym. Wydaje mi się więc, że jedyne, co możemy naprawdę pokazać, to to, że jądra, które są podgrafami, prawdopodobnie nie będą mniejsze niż 2k.

Falk Hüffner

$FPTAS$ $PFPT$

$Q=(I_Q, S_Q, f_Q, opt_Q)$ $NP$ $Q$ $FPTAS$ $Q$ $PFPT$

$PFPT$

$NP$ $Q$ $PFPT$ $O(|x|^{O(1)}k^{O(1)})$ $|x|$ $x$

Inne charakterystyki dla dwóch klas aproksymacyjnych zostały zaproponowane w [2, Twierdzenie 6.5].

Problemem jest

$PTAS$ $ptas^{\infty}$ $XP^w$

$FPTAS$ $fptas^{\infty}$ $PFPT^w$

$(f)ptas^{\infty}$ $(XP)PFPT^w$ $\frac{1}{\epsilon}$

Schematy aproksymacji czasu wielomianowego i sparametryzowana złożoność . J. Chen i in. / Discrete Applied Mathematics 155 (2007) 180–193.
Struktura aproksymacji czasu wielomianowego . EJ van Leeuwen i in. Raport techniczny UU-CS-2009-034, grudzień 2009.

Oleksandr Bondarenko
źródło