Jeśli to algorytm zwraca rozwiązanie optymalne. Jeżeli natomiast to algorytm jest jedynie heurystyką, a więc zwracane przez niego rozwiązanie może być dowolnie odległe od optimum.
Czasem dopuszcza się również, że ε jest pewną funkcją od wielkości danych
ρ-aproksymacja Algorytm A nazywamy ρ-aproksymacyjnym, jeśli dla dowolnych poprawnych danych wejściowych oraz
Wartość określa ile razy otrzymane rozwiązanie jest gorsze od optimum. Dokładniej dla problemu maksymalizacyjnego, dla problemu minimalizacyjnego.
W przypadku gdy algorytm zwraca rozwiązanie optymalne, Jeżeli rozwiązanie może być dowolnie odległe od optimum, to wartość jest nieskończonością.
Powyższe dwie definicje są od siebie zależne. Zachodzi równość Warto zauważyć, że nie ma potrzeby zaznaczania, która z powyższych definicji została wykorzystana przy określaniu konkretnego algorytmu, ponieważ (przypadek, w którym nie jest interesujący, gdyż wtedy mamy do czynienia z heurystyką), natomiast
Zobacz też L-redukcja w pełni wielomianowy schemat aproksymacji wielomianowy schemat aproksymacji
Bibliografia
Linki zewnętrzne Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems (en).