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