Algorytmy aproksymacyjne – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych.
Istotą algorytmu aproksymacyjnego, tym co odróżnia go od algorytmu heurystycznego, jest związana z każdym takim algorytmem informacja o koszcie zwracanego rozwiązania w stosunku do rozwiązania optymalnego. Mianowicie koszt rozwiązania zwróconego przez algorytm aproksymacyjny jest nie większy (w przypadku problemu minimalizacyjnego) albo nie mniejszy (w przypadku problemu maksymalizacyjnego) od rozwiązania optymalnego pomnożonego przez pewną stałą.
Definicja Załóżmy, że mamy dany konkretny problem optymalizacyjny. Niech oznacza zbiór dopuszczalnych rozwiązań tego problemu dla danych wejściowych Niech gdzie będzie funkcją kosztu rozwiązania dla tego problemu. Oznaczmy przez koszt rozwiązania optymalnego dla danych mianowicie dla problemu minimalizacyjnego oraz dla problemu maksymalizacyjnego.
ε-aproksymacja Algorytm A nazywamy ε-aproksymacyjnym, jeżeli dla dowolnych poprawnych danych wejściowych oraz
Przy takiej definicji zachodzi: dla problemu maksymalizacyjnego, dla problemu minimalizacyjnego.