Dureza de aproximação - erro aditivo

24

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.

Rafael
fonte
Qual é o título do livro que você mencionou?
Karolina Sołtys 23/10/10
2
Não tenho certeza se isso está certo. Veja a página 2 das notas vinculadas na pergunta, especificamente os teoremas 3 e 4 e o problema em aberto exposto logo abaixo do teorema 4. O livro em particular que eu estava me referindo é Algoritmos de Aproximação de Vijay Vazirani, o que é excelente.
Raphael
Frieze e Kannan ( research.microsoft.com/en-us/um/people/kannan/Papers/… ) forneceram um algoritmo aleatório de tempo constante com erro aditivo epsilon n ^ k para qualquer problema de satisfação de restrição máxima com restrições de arity k.
22710 Warren Schudy
Penso que a embalagem do caixote sendo aproximada no OPT + 1 é totalmente consistente com o conhecimento atual. De fato, a configuração LP é conjecturada para ter um intervalo de integralidade aditivo 1 (acho a conjectura um pouco selvagem, mas não há contra-exemplos conhecidos).
precisa

Respostas:

23

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

Tsuyoshi Ito
fonte
3
Como outro exemplo, acho que seria bastante natural formular o problema do corte máximo para maximizar a fração de arestas no corte. Novamente, temos resultados positivos e negativos para a aproximação aditiva.
Jukka Suomela 23/10/10
1
@Jukka, você poderia fornecer uma referência para esta formulação do Max-cut?
Mohammad Al-Turkistany
1
Muito obrigado. Parece que esta é uma área que precisa de pelo menos uma pesquisa. O zoológico de complexidade nem sequer menciona classes de aproximação de erro aditivo, tanto quanto eu posso ver (embora seja tão grande que eu possa ter perdido alguma coisa).
Raphael
@ Rafael: Eu acharia uma pesquisa (ou um ponteiro para uma) bastante útil. Até onde eu sei, as classes de algoritmos de aproximação foram pesquisadas pela última vez há cerca de dez anos, e eu achei a apresentação longe de ser clara.
András Salamon
6

Esta é uma resposta parcial

UMABSUMABS .

NP -completo enquanto cada gráfico planar é 4-colorível em tempo polinomial (pelo teorema de quatro cores).

-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.

UMABSP=NP

Mohammad Al-Turkistany
fonte
Obrigado. Percebo que o ABS não está listado no zoológico de complexidade qwiki.stanford.edu/index.php/Complexity_Zoo:A . Você tem uma referência para isso?
Raphael
Verifique esta referência, citeseerx.ist.psu.edu/viewdoc/…
Mohammad Al-Turkistany
Estou certo ao pensar que o nome ABS para a classe de complexidade é aquele que você acabou de cunhar ou existe uma referência para isso? O link que você postou não parece mencionar.
Raphael
@ Rafael, não, eu não inventei o nome ABS, li em algum lugar há muito tempo.
Mohammad Al-Turkistany
6

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.

Oleksandr Bondarenko
fonte