Wersja z 17:40, 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

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

@@ Linia 7: / Linia 7: @@
 * Komiwojażer
 ** Nie da się aproksymować
-** <math>2</math>-aproksymacja i <math>\fract{3}{2}</math>-aproksymacja przy warunku trójkąta
+** <math>2</math>-aproksymacja i <math>\frac{3}{2}</math>-aproksymacja przy warunku trójkąta
 * Plecak - <math>2</math>-aproksymacja
 * Kolorowanie wierzchołkowe nie da się aproksymować
@@ Linia 13: / Linia 13: @@
 * Pakowanie
 ** <math>2</math>-aproksymacja
-** nie ma <math>\fract{3}{2}-\epsilon</math>-aproksymacji
+** nie ma <math>\frac{3}{2}-\epsilon</math>-aproksymacji
 = Schematy aproksymacyjne =