Złożoność obliczeniowa/Moduł Schematy aproksymacji i klasa MAXSNP: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 10: | Linia 10: | ||
= klasa SNP i MAXSNP = | = klasa SNP i MAXSNP = | ||
* problem MAXSAT | |||
* problem zbioru niezależnego przy ograniczonym stopniu wierzchołka | |||
* problem maksymalnego podgrafu <math>k</math>-kolorowalnego | |||
* L-redukcje | * L-redukcje | ||
** redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka | ** redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka | ||
Wersja z 19:33, 1 lip 2006
Schematy aproksymacyjne
- PTAS i FPTAS
- PTAS i FPTAS dla plecaka
- asymptotyczny PTAS dla pakowania
- problem zbioru niezależnego albo posiada PTAS, albo nie posiada współczynnika aproksymacji
silna NP-zupełność
- przykłady
- problemy silnie NP-zupełne nie mają FPTAS
klasa SNP i MAXSNP
- problem MAXSAT
- problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
- problem maksymalnego podgrafu -kolorowalnego
- L-redukcje
- redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka
