L-redukcja

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 c_A i c_B 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

$OPT(R(x))\leqslant \alpha OPT(x)$

• istnieje taka dodatnia stała β, że

$|OPT(x)-c_{A}(S(y))|\leqslant \beta |OPT(R(x))-c_{B}(y)|$

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:

$\delta ={\frac {\alpha \beta \epsilon }{1-\epsilon }}$

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