Złożoność obliczeniowa/Moduł Algorytmy aproksymacyjne: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 7: | Linia 7: | ||
* Komiwojażer | * Komiwojażer | ||
** Nie da się aproksymować | ** Nie da się aproksymować | ||
** $2$-aproksymacja i $\fract{3}{2}$-aproksymacja przy warunku trójkąta | ** $$2$$-aproksymacja i $\fract{3}{2}$-aproksymacja przy warunku trójkąta | ||
* Plecak - $2$-aproksymacja | * Plecak - $2$-aproksymacja | ||
* Kolorowanie wierzchołkowe nie da się aproksymować | * Kolorowanie wierzchołkowe nie da się aproksymować | ||
Wersja z 17:37, 1 lip 2006
Definicje
- problem optymalizacyjny
- algorytm aproksymacyjny
- współczynnik aproksymacji
Przykłady
- Komiwojażer
- Nie da się aproksymować
- $$2$$-aproksymacja i $\fract{3}{2}$-aproksymacja przy warunku trójkąta
- Plecak - $2$-aproksymacja
- Kolorowanie wierzchołkowe nie da się aproksymować
- Kolorowanie krawędziowe
- Pakowanie
- $2$-aproksymacja
- nie ma $\fract{3}{2}-\epsilon$-aproksymacji
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
