Há uma literatura rica e pelo menos um livro muito bom que define a dureza conhecida dos resultados da aproximação para problemas difíceis de NP no contexto de erro multiplicativo (por exemplo, 2 aproximações para cobertura de vértices é ideal, considerando UGC). Isso também inclui classes de complexidade de aproximação bem conhecidas, como APX, PTAS e assim por diante.
O que se sabe quando o erro aditivo deve ser considerado? Uma pesquisa na literatura mostra alguns resultados do tipo limite superior, principalmente para empacotamento de lixeira (consulte, por exemplo, http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps ), mas existe uma classificação de classe de complexidade mais abrangente ou existe uma razão para não ser tão interessante ou relevante?
Como um comentário adicional, para empacotamento de lixeira, por exemplo, até onde eu sei não há razão teórica para que um algoritmo de tempo polifásico que esteja sempre a uma distância aditiva do ideal de 1 não possa ser encontrado (embora eu deva ser corrigido ) Esse algoritmo colapsaria alguma classe de complexidade ou teria algum outro efeito teórico significativo?
Edição: A frase-chave que eu não usei é "classe de aproximação assintótica" (graças Oleksandr). Parece que há algum trabalho nessa área, mas ainda não chegou ao mesmo estágio de maturidade que a teoria das classes clássicas de aproximação.
Respostas:
A pergunta é um tanto aberta, então não acho que possa ser respondida completamente. Esta é uma resposta parcial.
Uma observação fácil é que muitos problemas não são interessantes quando consideramos a aproximação aditiva. Por exemplo, tradicionalmente a função objetivo do problema Max-3SAT é o número de cláusulas satisfeitas. Nesta formulação, aproximar o Max-3SAT dentro de um erro aditivo O (1) é equivalente a resolver o Max-3SAT exatamente, simplesmente porque a função objetivo pode ser escalada copiando a fórmula de entrada várias vezes. A aproximação multiplicativa é muito mais essencial para os problemas desse tipo.
[Editar: Na revisão anterior, eu usei o Independent Set como exemplo no parágrafo anterior, mas mudei para Max-3SAT porque o Independent Set não é um bom exemplo para ilustrar a diferença entre aproximação multiplicativa e aproximação aditiva; Aproximando um conjunto independente, mesmo dentro de um fator multiplicativo O (1), também é NP-hard. De fato, Håstad [Has99].]
Mas, como você disse, a aproximação aditiva é interessante para problemas como empacotamento de lixeiras, onde não podemos dimensionar a função objetivo. Além disso, muitas vezes podemos reformular um problema para que a aproximação aditiva se torne interessante.
Por exemplo, se a função objetivo do Max-3SAT for redefinida como a razão entre o número de cláusulas satisfeitas e o número total de cláusulas (como às vezes é feito), a aproximação aditiva se tornará interessante. Nesse cenário, a aproximação aditiva não é mais difícil do que a aproximação multiplicativa, no sentido de que a aproximação dentro de um fator multiplicativo 1− ε (0 < ε <1) implica aproximação dentro de um erro aditivo ε , porque o valor ideal é sempre no máximo 1.
Um fato interessante (que infelizmente parece muitas vezes esquecido) é que muitos resultados de inadequação provam a completude de NP de certo decorre problemas de lacunaque não decorre da mera dureza NP da aproximação multiplicativa (ver também Petrank [Pet94] e Goldreich [Gol05, Seção 3]). Continuando o exemplo do Max-3SAT, é um resultado bem conhecido de Håstad [Has01] que é NP-difícil aproximar o Max-3SAT dentro de um fator multiplicativo constante melhor que 7/8. Esse resultado por si só não parece implicar que seja NP-difícil aproximar a versão de proporção do Max-3SAT dentro de um erro aditivo constante além de algum limite. No entanto, o que Håstad [Has01] prova é mais forte do que a mera falta de aproximação multiplicativa: ele prova que o seguinte problema de promessa é NP-completo para cada constante 7/8 < s <1:
Gap-3SAT s
Instância : fórmula φ Um CNF onde cada cláusula envolve exactamente três variáveis distintas.
Sim, prometo : φ é satisfatório.
Sem promessa : nenhuma atribuição de verdade satisfaz mais que a fração s das cláusulas de φ.
A partir disso, podemos concluir que é NP-difícil aproximar a versão de proporção do Max-3SAT dentro de um erro aditivo melhor que 1/8. Por outro lado, a atribuição aleatória simples e usual fornece aproximação dentro de um erro aditivo 1/8. Portanto, o resultado de Håstad [Has01] não apenas fornece a inadequação multiplicativa ideal para esse problema, mas também a inadequação aditiva ideal. Eu acho que existem muitos resultados adicionais de inadequação como esse que não aparecem explicitamente na literatura.
Referências
[Gol05] Oded Goldreich. Em problemas de promessa (uma pesquisa em memória de Shimon Even [1935-2004]). Colóquio Eletrônico sobre Complexidade Computacional , Relatório TR05-018, fevereiro de 2005. http://eccc.hpi-web.de/report/2005/018/
[Has99] Johan Håstad. É difícil aproximar o clique dentro de n 1− ε . Acta Mathematica , 182 (1): 105-142, março de 1999. http://www.springerlink.com/content/m68h3576646ll648/
[Has01] Johan Håstad. Alguns ótimos resultados de inadequação. Journal of the ACM , 48 (4): 798–859, julho de 2001. http://doi.acm.org/10.1145/502090.502098
[Pet94] Erez Petrank. A dureza da aproximação: localização da lacuna. Complexidade computacional , 4 (2): 133-157, abril de 1994. http://dx.doi.org/10.1007/BF01202286
fonte
Esta é uma resposta parcial
-Todos os gráficos cúbicos possuem bordas de 4 cores em tempo polinomial, mas a coloração de bordas 3 é difícil de NP.
fonte
Há um trabalho recente sobre classes de aproximação assintótica e sua comparação com contrapartes clássicas.
Erik Jan van Leeuwen e Jan van Leeuwen. Estrutura da aproximação do tempo polinomial . Relatório Técnico UU-CS-2009-034. Dezembro 2009.
fonte