Definição de PTAS vs. FPTAS

13

Pelo que li no preliminary version of a chapter of the book “Lectures on Scheduling” edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

Esta é a definição do PTAS :

Um esquema de aproximação de tempo polinomial ( PTAS ) para o problema é um esquema de aproximação cuja complexidade de tempo é polinomial no tamanho da entrada.X

e definição do FPTAS

Um esquema de aproximação de tempo totalmente polinomial ( FPTAS ) para o problema é um esquema de aproximação cuja complexidade de tempo é polinomial no tamanho da entrada e também polinomial em 1 / ϵ .Xϵ

Então o escritor diz:

Portanto, para um PTAS, seria aceitável ter uma complexidade de tempo proporcional a onde | I | é o tamanho da entrada; embora essa complexidade de tempo seja exponencial em 1 / ϵ . Um FPTAS não pode ter uma complexidade de tempo que cresça exponencialmente em 1 / ϵ, mas uma complexidade de tempo proporcional a | I | 8 / ε 3 seria ótimo. Com relação à aproximação dos piores casos, um FPTAS é o resultado mais forte possível que podemos obter para um problema difícil de NP.|I|1/ϵ|I|1/ϵ1/ϵ|I|8/ϵ3

Em seguida, ele sugeriu a figura a seguir para ilustrar os relacionamentos entre as classes de problemas:

insira a descrição da imagem aqui

Aqui estão as minhas perguntas:

  1. 1/ϵ

  2. (n+1/ϵ)3

  3. O que ele quer dizer com: um FPTAS é o resultado mais forte possível que podemos obter para um problema difícil de NP.

  4. No geral, eu gostaria de saber o que exatamente esses conceitos significam e quais são suas propriedades distintas.

Desde já, obrigado.

M ama D
fonte
(n+1/ϵ)3
1
Não poste mais de uma pergunta em um post, por favor. É bem possível que entender uma resposta para sua primeira pergunta faça o resto. (IMHO, o seu problema é que você não entende o que "e também polinômio em 1 / £" significa.)
Raphael
n
(n+1/ϵ)3n
@ RickyDemer você está certo, eu cometi um erro. Obrigado.
M AMA D

Respostas:

15

Deixe-me responder suas perguntas em ordem:

  1. n1+ϵn1/ϵO((n/ϵ)C)C021/ϵO((n/ϵ)C)C
    O((n/ϵ)C)O(nCeD/ϵ)ϵE1+1/nE

  2. 1+ϵ(n+1/ϵ)3ϵO(n3)n

  3. ϵϵϵnlog(1/ϵ)nlog(1/ϵ)

  4. C>11+ϵe1/ϵϵϵ1+1/nCC

Yuval Filmus
fonte
Por favor, não incentive comportamentos indesejáveis ​​de postagem.
Raphael
1

|I|=nϵn1/ϵnϵϵ1/ϵnpoly(n,1/ϵ)n4(1/ϵ)3+(1/ϵ)8n1/ϵn1/ϵ

Cyriac Antony
fonte
2
ϵϵϵϵ1/ϵ