Złożoność obliczeniowa/Moduł Schematy aproksymacji i klasa MAXSNP

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 MAXSNP

  • twierdzenie Fagina i definicja SNP
  • 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
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Moduł_Schematy_aproksymacji_i_klasa_MAXSNP&oldid=2627”