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 |
|||
| Linia 1: | Linia 1: | ||
Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]] | |||
= Schematy aproksymacyjne = | = Schematy aproksymacyjne = | ||
* PTAS i FPTAS | * PTAS i FPTAS | ||
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
