Wersja z 19:32, 1 lip 2006

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

- problem MAXSAT
- problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
- problem maksymalnego podgrafu $k$ -kolorowalnego
L-redukcje
- redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka

@@ Linia 1: / Linia 1: @@
-* klasa SNP i MAXSNP
+= 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
+= silna NP-zupełność =
+* przykłady
+* problemy silnie NP-zupełne nie mają FPTAS
+= klasa SNP i MAXSNP =
 ** problem MAXSAT
 ** problem zbioru niezależnego przy ograniczonym stopniu wierzchołka
@@ Linia 5: / Linia 15: @@
 * L-redukcje
 ** redukcja problemu zbioru niezależnego do pokrycia wierzchołkowego przy ograniczonym stopniu wierzchołka
-* MAX3SAT jest zupełny w MAXSNP w sensie L-redukcji
-* systemy dowodów propabilistycznie weryfikowalnych
-* twierdzenie <math>\mathbf{NP} = \mathbf{PCP}(\log n, 1)</math>
-* MAX3SAT nie ma PTAS, problemy z MAXSNP nie mają PTAS, problem zbioru niezależnego nie ma współczynnika aproksymacji