Złożoność obliczeniowa/Test 8: Schematy aproksymacji i klasa MAXSNP

Schemat aproksymacji Skrót FPTAS oznacza

to samo co PTAS, tylko dla problemów minimalizacji Źle

wielomianowy schemat aproksymacji, w którym złożoność jest wielomianowo zależna od odwrotności dokładności Dobrze

wielomianowy schemat aproksymacji Źle

wielomianowy schemat aproksymacji dla problemów silnie NP-zupełnych Źle

żadna z pozostałych odpowiedzi nie jest poprawna Źle

Schemat aproksymacyjny dla problemu plecakowego Algorytm zaokragleniowy dla problemu plecakowego

można łatwo przekształcić w algorytm aproksymacyjny o stałej $a=1/10$ Dobrze

wykorzystuje to, że KNAPSACK nie jest silnie NP-zupełny Dobrze

wykorzystuje to, że KNAPSACK jest problemem liczbowym Dobrze

jest PTAS i nie jest FPTAS Źle

wykorzystuje to, że KNAPSACK jest silnie NP-zupełny Źle

Algorytm pakowania dzielący na grupy Algorytm aproksymacyjny dla problemu pakowania dzielący przedmioty na grupy

jest wielomianowym schematem aproksymacyjnym Źle

jest asymptotycznym wielomianowym schematem aproksymacyjnym Dobrze

jest w pełni wielomianowym schematem aproksymacyjnym Źle

przez ustalenie dokładności staje sie algorytmem aproksymacyjnym o pewnej stałej aproksymacji Dobrze

L-redukcja $f$ z problemu A do problemu B

przekształca instancje problemu A w instancje problemu B Dobrze

przekształca rozwiązania dopuszczalne problemu A w rozwiązania dopuszczalne problemu B Źle

przekształca algorytm $a$-aproksymacyjny dla B w algorytm $a$-aproksymacyjny dla A Źle

gwarantuje, że $opt(f(I))\le \gamma opt(I)$ dla pewnej stałej $\gamma$ Dobrze

Problem zbioru niezależnego z ograniczeniem na stopień wierzchołka Standardowa redukcja z problemu INDEPENDENT SET do NODE COVER

przenosi skojarzeniowy algorytm aproksymacyjny na problem INDEPENDENT SET ze stałym współczynnikiem aproksymacji Źle

nie jest L-redukcją Dobrze

jest L-redukcją jeśli narzucamy ograniczenie przez stałą na stopień wierzchołka w obu problemach Dobrze

przenosi PTAS dla NODE COVER (jeśli istnieje) na INDEPENDENT SET, jeśli narzucamy ograniczenie przez stałą na stopień wierzchołka w obu problemach Dobrze

Klasa $MAXSN{P}_0$

pokrywa się z klasą problemów NP-optymalizacyjnych Źle

zawiera sie istotnie w MAXSNP Dobrze

zawiera problem MAX CUT vzawiera problem NODE COVER Dobrze

zawiera tylko takie problemy, które posiadają $a$-aproksymację, dla pewnej stałej $a$ Dobrze

Problem MAXkFSAT

ma strategię aproksymacyjną o stałej 1/2 Źle

ma strategię aproksymacyjną o stałej $1/2^k$ Dobrze

nie wiadomo, czy ma strategię aproksymacyjną o jakiejkolwiek stałej Źle

L-redukuje sie do MAX3SAT Dobrze