Redução com Preservação Aproximada

Em teoria da computabilidade e complexidade computacional, especialmente no estudo de algoritmos de aproximação, uma redução com preservação aproximada é um algoritmo para transformar um problema de otimização em outro problema qualquer, de tal forma que a distância para uma solução ideal é preservada em algum grau. Reduções com preservação aproximada são um subconjunto das mais gerais reduções na teoria da complexidade; a diferença é que a redução com preservação aproximada geralmente criam sentenças sobre a aproximação de problemas ou de problemas de otimização, como oposição aos problemas de decisão.

Intuitivamente, um problema  A é redutível ao problema B através de uma aproximação, preservando a redução se, dada uma instância de problema A e um (possivelmente aproximado) solucionador para o problema B, pode-se converter a instância de problema A em uma instância do problema B, aplicar o solucionador para o problema B, e recuperar uma solução para o problema A que também tem alguma garantia de aproximação.

Definição

Ao contrário de reduções em problemas de decisão, uma redução com preservação aproximada deve preservar mais do que a verdade das instâncias do problema quando reduzido de um problema para outro. Ele também deve manter algum tipo de garantia sobre a relação entre o custo da solução ideal em ambos os problemas. Para formalizar:

Seja $A$ e $B$ problemas de otimização.

Seja $x$ uma instância do problema $A$, com a melhor solução $OPT(x)$. Seja $c_{A}(x,y)$  o custo de uma solução $y$ para uma instância $x$ do problema $A$. Esta também é a métrica utilizada para determinar qual a solução que é considerada ideal.

Uma redução com preservação aproximada é um par de funções $(f,g)$ (que muitas vezes devem ser computáveis em tempo polinomial), tal que:

• $f$ mapeia um exemplo $x$ de $A$ em uma instância $x'$ de $B$.
• $g$ mapeia uma solução $y'$ de $B$ em uma solução $y$ de $A$.
• $g$ preserva alguma garantia do desempenho da solução, ou a taxa de aproximação, definida como $R_{A}(x,y)=\max \left({\frac {c_{A}(x,OPT(x))}{c_{A}(x,y)}},{\frac {c_{A}(x,y)}{c_{A}(x,OPT(x))}}\right)$.

Tipos de reduções com preservação aproximada

Há muitos tipos diferentes de reduções com preservação aproximada, todas com uma garantia diferente (o terceiro ponto na definição acima). No entanto, diferentemente do que ocorre com outras reduções, a redução com preservação aproximada, muitas vezes, sobrepõe-se em propriedades que eles demonstram em problemas de otimização (por exemplo, os membros da classe de complexidade ou completude, ou não aproximação). Os diferentes tipos de reduções são usados em vez de variar as técnicas de redução, em que a redução aplicável, que é mais facilmente adaptada ao problema é usada.

Nem todos os tipos de reduções com preservação aproximada podem ser usados para mostrar a associação em todos da classe da complexidade de aproximação, as mais notáveis são as APMS e APX. Uma redução abaixo preserva a associação em uma complexidade de classe C se, dado um problema A, que reduz o problema B através de um esquema de redução, e B esta em C, então A também esta em C. Algumas reduções mostradas abaixo apenas preservam a associação APX ou PTAS, mas não a outra. Devido a isso, o cuidado com a escolha deve ser feita quando se seleciona uma redução com preservação aproximada, especialmente para o propósito de provar a completude de um problema dentro de uma complexidade de classe.

Crescenzi sugere que os tres tipos de redução mais ideais, tanto para a facilidade de uso e poder de prova, são a redução PTAS, redução AP e L-redução. As descrições de redução que se seguem são de levantamento de Crescenzi de reduções com preservação aproximada.

Redução Restrita

A Redução restrita é o tipo mais simples de redução com preservação aproximada. Em uma redução rigorosa, a relação de aproximação de uma solução y' para uma instância x' de um problema B deve ser no máximo tão boa quanto a razão de aproximação da solução correspondente ao exemplo y para uma instancia x do problema A. Em outras palavras: 

$R_{A}(x,y)\leq R_{B}(x',y')$ for $x'=f(x),y=g(y')$.

Redução rigorosa é a mais simples: se uma redução rigorosa do problema A para o problema B existe, então o problema A sempre pode ser aproximado pelo menos a uma razão tão boa quanto um problema B. A redução rigorosa preserva a associação em ambos os PTAS e APX.

Existe um conceito semelhante de um S-redução, para o qual $c_{A}(x,y)=c_{B}(x',y')$, e a ótima das duas instâncias correspondentes devem ter o mesmo custo. S-redução é um caso muito especial de redução rigorosa, e é ainda mais restrita. Em efeito, os dois problemas A e B devem estar em perfeita correspondência entre si. A existência de um S-redução, implica não apenas na existência de uma redução rigorosa, mas em todas as outras reduções listadas aqui.

L-redução

L-redução preserva associações APMS bem como APX (mas só para a minimização de problemas no caso do APX). Como resultado, eles não podem ser utilizados, em geral, para provar completude sobre APX, Log-APX, ou Poli-APX, mas, no entanto, eles são valorizados pela sua formulação natural e facilidade de uso em provas.

PTAS-redução

PTAS-redução é um outro esquema de redução comumente utilizado. Embora ele preserve a associação nas PTAS, ele não faz isso para APX. No entanto, APX-completude é definida em termos de PTAS-reduções.

As PTAS-reduções são uma generalização da P-redução, mostrado abaixo, com a única diferença de que a função $g$ pode depender da relação de aproximação $r$.

A-redução e P-redução

A-redução e P-redução são esquemas de redução semelhantes que podem ser usados para mostrar a associação em APX e APMS, respectivamente. Ambos introduzem uma nova função $c$, definida em números maiores do que 1, o qual deve ser computável.

Em uma A-redução, temos que

$R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq c(r)$.

Em uma P-redução, temos que

$R_{B}(x',y')\leq c(r)\rightarrow R_{A}(x,y)\leq r$.

A existência de um P-redução implica na existência de um PTAS-redução.

E-redução

E-redução, que é uma generalização da redução rigorosa, mas implica na A-redução e na P-redução, é um exemplo de uma forma menos restritiva de tipo de redução que preserva a associação não só em PTAS e APX, mas também em classes maiores como Log-APX e Poli-APX. E-redução introduz dois novos parâmetros, um polinômio $p$ e uma constante $\beta$. A sua definição é a seguinte.

Em uma E-redução, temos que para algum polinômio $p$ e constante $\beta$,

• $c_{B}(OPT_{B}(x'))\leq p(|x|)c_{A}(OPT_{A}(x))$, onde $|x|$ denota o tamanho do problema, a exemplo da descrição.
• Para qualquer solução $y'$ para $B$, nós temos $R_{A}(x,y)\leq 1+\beta \cdot (R_{B}(x',y')-1)$.

Para obter uma A-redução de uma E-redução, seja $c(r)=1+\beta \cdot (r-1)$, e para obter um P-redução de uma E-redução, seja $c(r)=1+(r-1)/\beta$.

AP-redução

AP-reduções são usadas para definir a completude nas classes Log-APX e Poli-APX. Eles são um caso especial de PTAS-redução, reunindo as seguintes restrições.

Em um AP-redução, temos que, para alguma constante $\alpha$,

$R_{B}(x',y')\leq r\rightarrow R_{A}(x,y)\leq 1+\alpha \cdot (r-1)$

com a generalização adicional de que a função $g$ é permitida dependem da relação de aproximação $r$, como na PTAS-redução.

AP-redução também é uma generalização do E-redução. Uma restrição adicional, na verdade, precisa ser imposta para a AP-redução para preservar a associação do Log-APX e do Poli-APX, como a E-redução faz: para problema de tamanho corrigido, o tempo de computação de $f,g$ não deve aumentar enquanto a relação de aproximação aumenta.

Gap redução

Uma gap redução é um tipo de redução que, embora útil para a demonstração de alguns resultados não aproximados, não se assemelha a outras reduções mostradas aqui. Gap reduções lidam com problemas de otimização dentro de um recipiente de problema de decisão, gerado alterando o problema objetivo para distinguir entre a solução ótima e soluções de alguns fatores multiplicativos piores do que o ideal.

Veja também

• (Redução de complexidade)
• As APMS redução
• L-redução
• Algoritmo de aproximação