Złożoność obliczeniowa/Moduł Algorytmy aproksymacyjne: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Nie podano opisu zmian
 
Nie podano opisu zmian
 
(Nie pokazano 4 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]]
= Definicje =
= Definicje =
* problem optymalizacyjny
* problem optymalizacyjny
Linia 7: Linia 8:
* Komiwojażer
* Komiwojażer
** Nie da się aproksymować
** Nie da się aproksymować
** $2$-aproksymacja i $\fract{3}{2}$-aproksymacja przy warunku trójkąta
** <math>2</math>-aproksymacja i <math>\frac{3}{2}</math>-aproksymacja przy warunku trójkąta
* Plecak - $2$-aproksymacja
* 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
** $2$-aproksymacja
** <math>2</math>-aproksymacja
** nie ma $\fract{3}{2}-\epsilon$-aproksymacji
** nie ma <math>\frac{3}{2}-\epsilon</math>-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

Aktualna wersja na dzień 21:42, 1 lip 2006

Odpowiedzialny: Grzegorz Gutowski

Definicje

  • problem optymalizacyjny
  • algorytm aproksymacyjny
  • współczynnik aproksymacji

Przykłady

  • Komiwojażer
    • Nie da się aproksymować
    • 2-aproksymacja i 32-aproksymacja przy warunku trójkąta
  • Plecak - 2-aproksymacja
  • Kolorowanie wierzchołkowe nie da się aproksymować
  • Kolorowanie krawędziowe
  • Pakowanie
    • 2-aproksymacja
    • nie ma 32−ϵ-aproksymacji
  • ?
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Moduł_Algorytmy_aproksymacyjne&oldid=2634”