Esquema de aproximação de tempo polinomial

Em ciência da computação, um esquema de aproximação de tempo polinomial (PTAS) é um tipo de algoritmo de aproximação para problemas de otimização (na maioria das vezes, problemas de otimização NP-difíceis).

Um PTAS é um algoritmo que toma como entrada uma instância de um problema de otimização e um parâmetro $\varepsilon >0$ e, em tempo polinomial, produz uma solução que está dentro de um fator $1+\varepsilon$ de ser ideal (ou $1-\varepsilon$ para problemas de maximização). Por exemplo, para problema do caixeiro viajante Euclidiano, um PTAS iria produzir um percurso com duração no máximo $(1+\varepsilon )L$ , com $L$ sendo o comprimento do menor percurso .^[1]

O tempo de execução de um PTAS é necessariamente polinomial em n para cada ε fixado, mas pode ser diferente para diferentes ε. Assim, um algoritmo sendo executado em tempo $O(n^{1/\varepsilon })$ , ou mesmo $O(n^{\exp {1/\varepsilon }})$ conta como um PTAS.

Variantes[editar | editar código-fonte]

Deterministica[editar | editar código-fonte]

Um problema prático com os algoritmos de PTAS é que o expoente do polinômio poderia aumentar dramaticamente à medida que ε diminui, por exemplo, se o tempo de execução for $O(n^{1/\varepsilon })$ . Uma forma de lidar com isso é definir o esquema de aproximação eficiente em tempo polinomial ou EPTAS, em que o tempo de execução é necessário que seja $O(n^{c})$ para uma constante $c$ independente de $\varepsilon$ . Isso garante que um aumento no tamanho de problema tem o mesmo efeito relativo em tempo de execução, independentemente do $\varepsilon$ que está sendo usado; no entanto, a constante sob o big-O pode ainda depender de $\varepsilon$ arbitrariamente. Ainda mais restritivo, e útil na prática, é o esquema de aproximação totalmente em tempo polinomial ou FPTAS, que requer que o algoritmo seja polinomial em ambos os problema de tamanho $n$ e $1/\varepsilon$ . Todos os problemas em FPTAS são tratáveis com parâmetros de tamanho fixo. Um exemplo de um problema que tem uma FPTAS é o Problema da mochila.

Qualquer problema de otimização fortemente NP-difícil com uma função objetiva delimitada polinomialmente pode ter um FPTAS, a menos que P=NP.^[2] No entanto, o inverso falha: por exemplo, se P não é igual a NP, o problema da mochila com duas restrições não é fortemente NP-difícil, mas não tem FPTAS mesmo quando o objetivo ótimo é polinomialmente limitado.^[3]

A menos que P = NP, considera-se que FPTAS ⊊ APMS ⊊ APX.^[4] por conseguinte, com este pressuposto, problemas APX-difícil não têm PTASs.

Outra variante determinística PTAS é o esquema de aproximação quase em tempo polinomial ou QPTAS. Um QPTAS tem complexidade de tempo $n^{polylog(n)}$ para cada $\epsilon >0$ fixado.

Randomizado[editar | editar código-fonte]

Alguns problemas que não têm uma PTAS podem admitir que um algoritmo randomizado com propriedades semelhantes, esquema de aproximalção em tempo polinomial randomizados ou PRAS. Um PRAS é um algoritmo que leva uma instância de uma otimização ou problema de contagem e um parâmetro $\varepsilon >0$ e, em tempo polinomial, produz uma solução que tem uma alta probabilidade de estar dentro de um fator $\varepsilon$ do ideal. Convencionalmente, a "alta probabilidade" significa probabilidade maior que 3/4, embora, como com a maioria das classes de complexidade probabilísticas a definição é robusta a variações neste valor exato (o mínimo requisito é geralmente maior do que 1/2). Como um PTAS, um PRAS deve ter o tempo de execução polinomial em n, mas não necessariamente em $\varepsilon$ ; com mais restrições sobre o tempo de execução em $\varepsilon$ , pode-se definir um esquema de aproximação eficiente em tempo polinomial randomizados ou EPRAS semelhante à EPTAS, e um esquema de aproximação totalmente em tempo polinomial randomizados ou FPRAS semelhante à FPTAS.^[2]

Como uma complexidade de classe[editar | editar código-fonte]

O termo PTAS também pode ser usado para se referir à classe de problemas de otimização que tem um PTAS. PTAS é um subconjunto de APX, e a menos que P = NP, é um subconjunto estrito.^[4]

A presença em PTAS pode ser demonstrada utilizando uma Redução PTAS, Redução linear, ou P-redução, as quais preservam a presença em PTAS, e estes também podem ser utilizados para demonstrar a PTAS-completude. Por outro lado, mostrar a não presença em PTAS (ou seja, a não-existência de um PTAS), pode ser feita mostrando que o problema é APX-difícil, após o qual a existência de um PTAS iria mostrar P = NP. APX-dificuldade é geralmente mostrado através de uma redução PTAS redução ou AP-redução.

Referências

↑ Sanjeev Arora, em tempo Polinomial Aproximação Esquemas para Euclidiana TSP e outros Problemas Geométricos, Revista da ACM 45(5) 753-782, 1998.
↑ ^a ^b Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8
↑ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. [S.l.]: Springer
↑ ^a ^b Jansen, Thomas (1998), «Introduction to the Theory of Complexity and Approximation Algorithms», in: Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika, Lectures on Proof Verification and Approximation Algorithms, ISBN 9783540642015, Springer, pp. 5–28, doi:10.1007/BFb0053011 .

Ligações externas[editar | editar código-fonte]

A complexidade do Zoo: APMS, EPTAS, FPTAS
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, e Gerhard Woeginger, Um compêndio de problemas de otimização NP – lista de problemas de otimização NP tem PTAS.

[1] Sanjeev Arora, em tempo Polinomial Aproximação Esquemas para Euclidiana TSP e outros Problemas Geométricos, Revista da ACM 45(5) 753-782, 1998.

[vvv-2] Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8

[3] H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. [S.l.]: Springer

[Jansen-4] Jansen, Thomas (1998), «Introduction to the Theory of Complexity and Approximation Algorithms», in: Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika, Lectures on Proof Verification and Approximation Algorithms, ISBN 9783540642015, Springer, pp. 5–28, doi:10.1007/BFb0053011 .

[1]

[2]

[3]

[4]