Redução linear

Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação. Nos estudos de aproximação de problemas de otimização as reduções lineares desempenham um papel semelhante ao de reduções polinomiais no estudos da complexidade computacional de problemas de decisão.

O termo L-redução é por vezes utilizado para se referir a reduções em espaço logarítmico, por analogia com a classe de complexidade L, mas isto é um conceito diferente.

Definição

Sejam A e B problemas de otimização e c_A e c_B suas respetivas funções de custo. Um par de funções f e g é uma L-redução se todas as seguintes condições são encontradas:

• funções f e g são computáveis em tempo polinomial,
• se x é uma instância do problema A, então f(x) é uma instância do problema B,
• se y é a solução para f(x), então g(y) é a solução para x,
• existe uma constante positiva α tal que

$\mathrm {OPT_{B}} (f(x))\leq \alpha \mathrm {OPT_{A}} (x)$,

• existe uma constante positiva β tal que para toda solução y para f(x)

$|\mathrm {OPT_{A}} (x)-c_{A}(g(y))|\leq \beta |\mathrm {OPT_{B}} (f(x))-c_{B}(y)|$.

Propriedades

Seja f uma (1±ε)-algoritmo de aproximação para o problema A tal que $c_{\mathrm {A} }(f(x))$ é no máximo $\varepsilon \cdot \mathrm {OPT_{A}} (x)$ distante de $\mathrm {OPT_{A}} (x)$, para toda instância de x. (Nesta notação, + implicitamente significa um problema de minimização, e $-$ significa um problema de maximização.)

O ponto principal de uma L-redução é o seguinte: dado uma (f,g,α,β) L-redução do problema A para o problema B, e um (1±ε)-algoritmo de aproximação para B, nós obtemos em tempo polinomial um (1±δ)-algoritmo de aproximação para A onde $\delta =\alpha \beta \varepsilon$. Isto implica que se B tem um esquema de aproximação em tempo polinomial (PTAS) então A também terá.

Ver também

• MAXSNP
• Redução PTAS
• Conjunto dominante#L-reduções: um exemplo com α = β = 1

Referências

• Pierluigi Crescenzi: A Short Guide to Approximation Preserving Reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, June 24-27, 1997, Ulm, Germany. Pages 262-273. IEEE Computer Society Press, 1997. ISBN 0-8186-7907-7
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation. Combinatorial optimization problems and their approximability properties. 1999, Springer. ISBN 3-540-65431-3