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

Definicje

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

Przykłady

• Komiwojażer
  • Nie da się aproksymować
  • $2$-aproksymacja i $\frac{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 $\frac{3}{2}-ϵ$-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