L-redukcja – transformacja problemów optymalizacyjnych, która zachowuje własności aproksymacyjne. L-redukcje odgrywają podobną rolę w badaniach nad aproksymowalnością problemów optymalizacyjnych, jak transformacje wielomianowe w badaniach nad złożonością obliczeniową problemów decyzyjnych.
Definicja Niech A i B będą problemami optymalizacyjnymi a cA i cB ich odpowiednimi funkcjami kosztu. Parę funkcji R i S nazywamy L-redukcją problemu A do B jeśli spełnione są następujące warunki: funkcje R i S da się obliczyć w logarytmicznej pamięci, jeśli x jest instancją problemu A, to R(x) jest instancja problemu B, jeśli y jest rozwiązaniem R(x) to S(y) jest rozwiązaniem x, istnieje taka dodatnia stała α, że
istnieje taka dodatnia stała β, że
Własności Można pokazać, że jeśli (R, S) jest L-redukcją problemu A do B i istnieje wielomianowy algorytm ε-aproksymacyjny dla A to istnieje wielomianowy algorytm δ-aproksymacyjny dla B gdzie:
gdzie α i β są stałymi z definicji powyżej. Z tego wynika, ze jeśli istnieje wielomianowy schemat aproksymacji dla A to istnieje wielomianowy schemat aproksymacji dla B.
Zobacz też algorytm aproksymacyjny problem NP zupełny
Kategoria:Algorytmy aproksymacyjne