1. ALGORYTMY PRZYBLIŻONE

1. Analiza

1. Analiza eksperymentalna – wygenerowanie pewnego zbioru X instancji badanego problemu Π oraz rozwiązanie wszystkich tych instancji badanym algorytmem A

Ocena jakości algorytmu - Średnia odległość od optimum, maksymalna odległość od optimum

1. Analiza probabilistyczna

1. Analiza najgorszego przypadku

1. Współczynnik osiągalności aproksymacyjnej – współczynnik najgorszego przypadku dla problemu Π opisany wzorem:

1. Schematy aproksymacyjne

1. PTAS – wielomianowe schematy aproksymacyjne

1. FPTAS – w pełni wielomianowe schematy aproksymacyjne

1. Zakres stosowalności