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

Odpowiedzialny: Grzegorz Gutowski

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
• ?