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 Parser nie mógł rozpoznać (nieznana funkcja „\fract”): {\displaystyle \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 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