Wiele problemow na jakie można natknąć się w rzeczywistości jest NP-trudnych. Dla nich nie istnieją (najprawdopodobniej) algorytmy działające w sensownym (wielomianowym) czasie i podające optymalne rozwiązania.
Możemy zrelaksować nasze wymagania i chcieć otrzymywać rozwiązania niekoniecznie optymalne, ale jednak w miarę bliskie optymalnym.
Algorytm aproksymacyjny o wspołczynniku a (algorytm a-aproksymacyjny) to wielomianowy algorytm, ktory oblicza rozwiązanie co najwyżej a razy gorsze
od optymalnego. Rożne problemy dopuszczają rożny stopień aproksymowalności.
Dla niektorych znane są algorytmy o stałym wspołczynniku (np. 8/7 lub 2),
dla niektorych znane są algorytmy o wspołczynniku, ktory jest funkcją
wielkości instancji (np. log n) . Czasami wiadomo, że skonstruowanie
algorytmu apr. o stałym wspołczynniku lub o wspołczynniku lepszym niż pewna stała (np. 761/760)
jest NP-trudne. A niektorych problemow właściwie w ogole nie daje się aproksymować.
**Wymagane przygotowanie studentów:**
Algorytmy i struktury danych
Matematyka dyskretna
1. Algorytmy aproksymacyjne kombinatoryczne m.in. dla problemow
-set cover,
-komiwojażera,
-najkrotszego superstringa,
-pokrycia wierczhołkowego,
-bin packing,
-schedulingu.
2. Algorytmy aproksymacyjne oparte na rożne sposoby o programowanie liniowe.
(Programowania liniowego nie trzeba znać przychodząc na wykł.)
3. Nieaproksymowalność niektorych problemow.
V.V.Vazirani "Approximation Algorithms"
D.P. Williamson, D.B. Shmoys "The Design of Approximation Algorithms"
artykuły czasopismowe i konferencyjne
