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

From Studia Informatyczne

Skrót FPTAS oznacza

to samo co PTAS, tylko dla problemów minimalizacji

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

wielomianowy schemat aproksymacji

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

żadna z pozostałych odpowiedzi nie jest poprawna


Algorytm zaokragleniowy dla problemu plecakowego

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

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

wykorzystuje to, że KNAPSACK jest problemem liczbowym

jest PTAS i nie jest FPTAS

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


Algorytm aproksymacyjny dla problemu pakowania dzielący przedmioty na grupy

jest wielomianowym schematem aproksymacyjnym

jest asymptotycznym wielomianowym schematem aproksymacyjnym

jest w pełni wielomianowym schematem aproksymacyjnym

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


L-redukcja f z problemu A do problemu B

przekształca instancje problemu A w instancje problemu B

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

przekształca algorytm a-aproksymacyjny dla B w algorytm a-aproksymacyjny dla A

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


Standardowa redukcja z problemu INDEPENDENT SET do NODE COVER

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

nie jest L-redukcją

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

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


Klasa MAXSNP_0

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

zawiera sie istotnie w MAXSNP

zawiera problem MAX CUT vzawiera problem NODE COVER

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


Problem MAXkFSAT

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

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

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

L-redukuje sie do MAX3SAT