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 |
||
| (Nie pokazano 2 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]] | |||
= Schematy aproksymacyjne = | = Schematy aproksymacyjne = | ||
* PTAS i FPTAS | * PTAS i FPTAS | ||
| Linia 9: | Linia 10: | ||
* problemy silnie NP-zupełne nie mają FPTAS | * problemy silnie NP-zupełne nie mają FPTAS | ||
= klasa | = klasa MAXSNP = | ||
* twierdzenie Fagina i definicja SNP | |||
* problem MAXSAT | * problem MAXSAT | ||
* problem zbioru niezależnego przy ograniczonym stopniu wierzchołka | * problem zbioru niezależnego przy ograniczonym stopniu wierzchołka | ||
Aktualna wersja na dzień 21:42, 1 lip 2006
Odpowiedzialny: Grzegorz Gutowski
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 MAXSNP
- twierdzenie Fagina i definicja SNP
- 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
