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

Definicje

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
?

@@ Linia 1: / Linia 1: @@
+Odpowiedzialny: [[Użytkownik:Ggutowski|Grzegorz Gutowski]]
 = Definicje =
 * problem optymalizacyjny
@@ Linia 14: / Linia 15: @@
 ** <math>2</math>-aproksymacja
 ** 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