Złożoność obliczeniowa/Moduł Algorytmy aproksymacyjne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Moduł_Algorytmy_aproksymacyjne&oldid=2618”