Algoritmos de aproximação para problemas em P

Geralmente, pensa-se em aproximar soluções (com garantias) a problemas difíceis de NP. Existe alguma pesquisa em andamento sobre problemas já conhecidos em P? Essa pode ser uma boa ideia por vários motivos. De cabeça para baixo, um algoritmo de aproximação pode ser executado com uma complexidade muito menor (ou até uma constante muito menor), pode usar menos espaço ou pode ser muito melhor paralelizável.

Além disso, os esquemas que fornecem compensações de tempo / precisão (FPTAS e PTAS) podem ser muito atraentes para problemas em P com limites mais baixos que são inaceitáveis ​​em entradas grandes.

Três perguntas: falta alguma coisa que torne isso obviamente uma má idéia? Há pesquisas em andamento no desenvolvimento de uma teoria desses algoritmos? Se não, pelo menos, alguém está familiarizado com exemplos individuais de tais algoritmos?

Como Jukka aponta, a geometria computacional é uma fonte rica de problemas que podem ser resolvidos em tempo polinomial, mas desejamos obter aproximações rápidas. O resultado "ideal" clássico é um "LTAS" (esquema de aproximação de tempo linear) cujo tempo de execução seria da forma - geralmente, estes são obtidos pela extração de uma constante (poli ( )) do tamanho de dados e executando um algoritmo caro nesse kernel, com garantia de que uma solução exata no kernel é uma solução aproximada em toda a entrada.$O(n + \text{poly}(1/\epsilon))$$1/\epsilon$

Existem vários truques, reduções e princípios, e o novo livro de Sariel Har-Peled está cheio deles. Eu não acho que exista uma rica teoria da complexidade como tal.

Lista não exaustiva de artigos recentes que encontram soluções aproximadas para problemas em$P$

1) Há uma grande quantidade de trabalho em soluções aproximadas para equações lineares (simétricas na diagonal dominante) em tempo quase linear$\mathcal{O}(n\cdot\text{polylog}(n))$

(lista de artigos) http://cs-www.cs.yale.edu/homes/spielman/precon/precon.html

(Em geral, a maioria dos solucionadores iterativos de equações lineares compartilha o princípio de - aproximando a solução verdadeira. O mesmo vale para métodos iterativos que resolvem problemas mais gerais (por exemplo, alguns programas convexos / lineares)).$\epsilon$

2) Soluções aproximadas para min / max cortes / fluxos http://people.csail.mit.edu/madry/docs/maxflow.pdf$s-t$

3) Encontrar uma aproximação esparsa da transformada de Fourier de um sinal em tempo sublinear http://arxiv.org/pdf/1201.2501v1.pdf

4) Encontrar o componente principal aproximado de uma matriz http://www.stanford.edu/~montanar/RESEARCH/FILEPAP/GossipPCA.pdf

Não estou ciente de uma teoria geral sendo desenvolvida em algoritmos de aproximação para problemas em P. Conheço um problema em particular, porém, chamado de oráculos de distância aproximada:

Dado um gráfico não direcionado ponderado, comnós embordas, uma consulta de ponto-a-ponto pede a distância entre dois nós .n = | V | m = | E | s , t ∈ $G = (V, E)$$n = |V|$$m = |E|$$s, t \in V$

Há uma troca de três vias entre espaço, tempo de consulta e aproximação no problema do oráculo à distância. Pode-se responder trivialmente a cada consulta exatamente (aproximação = ) em tempo armazenando a matriz de distância de todos os pares; ou no tempo executando um algoritmo de caminho mais curto. Para gráficos massivos, essas duas soluções podem exigir um espaço proibitivamente grande (para armazenar a matriz) ou tempo de consulta (para executar um algoritmo de caminho mais curto). Por isso, permitimos aproximação.O ( 1 ) O ( m + n log n $1$$O(1)$$O(m + n\log n)$

Para gráficos gerais, o estado da arte é o oráculo de distância de Thorup e Zwick , que, para qualquer aproximação , requer um espaço ideal. Também oferece uma boa troca de aproximação de espaço.$k$

Para gráficos esparsos, pode ser mostrada uma troca mais geral de espaço-aproximação-tempo .

Muitas vezes, procuramos soluções aproximadas para problemas simples, como encontrar o caminho mais curto em um gráfico, encontrar o número de elementos únicos em um conjunto. A restrição aqui é que a entrada é grande e queremos resolver o problema aproximadamente usando uma única passagem sobre os dados. Existem vários algoritmos de "streaming" projetados para obter soluções aproximadas em tempo linear / quase linear.

$O(nm)$$n$$m$

São conhecidos algoritmos de aproximação rápida para a correspondência máxima. Pelo menos um que me vem à mente imediatamente é http://arxiv.org/pdf/1112.0790v1.pdf .

$P$

Eu acho que toda a área de streaming de dados e algoritmos sub-lineares é um esforço nessa direção. No fluxo de dados, o foco é resolver os problemas no espaço o (n) e O (polilog (n)) idealmente, enquanto nos algoritmos sub-lineares você tenta obter algoritmos com o (n) tempo de execução. Em ambos os casos, muitas vezes é preciso comprometer o algoritmo de aproximação aleatória.

Você pode começar com o material desta página e disso .

$\epsilon$$\epsilon$. Existem vários trabalhos sobre a solução de casos especiais de problemas de programação linear, como fluxos multicomodidades (e mais geralmente empacotando e cobrindo LPs) aproximadamente. Não existe uma teoria separada de aproximação para problemas em P versus problemas que estão em NP (não sabemos se P é igual a NP ou não). Pode-se falar sobre uma certa técnica ser aplicável a uma certa classe de problemas. Por exemplo, existem técnicas gerais conhecidas por resolver aproximadamente empacotar e cobrir programas lineares e algumas variantes.

Dimitris menciona aproximações de transformadas de Fourier. existe um amplo uso disso na compactação de imagem, por exemplo, no algoritmo JPEG. [1] embora eu não tenha visto um artigo que enfatize isso, parece, em certo sentido, que uma compressão com perda [2] (com limites deriváveis) também pode ser tomada como um algoritmo de aproximação no tempo P. os aspectos de aproximação são altamente desenvolvidos e ajustados / especializados no sentido de serem otimizados para que não possam ser percebidos pela visão humana, ou seja, a percepção humana de artefatos de codificação (aproximadamente definida como diferença entre aproximação e compressão sem perdas) é minimizada.

isso está relacionado a teorias sobre como o olho humano percebe ou a si mesmo "aproxima-se" da codificação de cores por meio de algum processo semelhante a algoritmo. em outras palavras, o esquema / algoritmo teórico de aproximação é realmente intencionalmente projetado para corresponder ao esquema / algoritmo de aproximação físico / biológico (codificado pelo processamento de informações biológicas, isto é, neurônios no sistema visual humano).

portanto, a compressão está fortemente acoplada à aproximação. em JPEG, a transformada de Fourier é aproximada pela DCT, transformada discreta de cosseno [3]. princípios semelhantes são empregados em vários quadros para o padrão de compressão de vídeo MPEG. [4]

[1] compressão jpeg, wikipedia

[2] compressão com perdas, wikipedia

[3] DCT, transformação discreta de cosseno, wikipedia

[4] MPEG, Wikipedia

Pode ser que isso não seja exatamente uma resposta à sua pergunta, porque atualmente posso me lembrar de algumas heurísticas, mas tenho certeza de que existem algumas aproximações, porque eu as vi antes.

$O(f(k)*|G|^\alpha)$$f(k)$ problema e suas aproximações / heurísticas posteriores (o Google simples mostra resultados em 2010, 2011) ou algoritmos para encontrar a decomposição em árvore de gráficos.

http://www.sciencedirect.com/science/article/pii/S0020019002003939

é um link para o artigo "Um algoritmo de aproximação simples para o problema de correspondência ponderada", de Doratha Drake e Stefan Hougardy, cobrindo o problema de correspondência ponderada.