L-redukcja
Z Wikipedii
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.
[edytuj] 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
[edytuj] 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.
