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.

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

${\displaystyle OPT(R(x))\leqslant \alpha OPT(x)}$

• istnieje taka dodatnia stała β, że

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

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:

${\displaystyle \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.

• algorytm aproksymacyjny
• problem NP zupełny