Trade-off de aproximação espacial

14

Em seu artigo Approximate Distance Oracles , Thorup e Zwick mostraram que, para qualquer gráfico não direcionado ponderado, é possível construir uma estrutura de dados do tamanho que possa retornar uma aproximação ( 2 k - 1 ) distância entre qualquer par de vértices no gráfico.O(kn1+1/k)(2k-1)

Em um nível fundamental, essa construção alcança um compromisso de aproximação de espaço - é possível reduzir os requisitos de espaço ao custo de uma "qualidade" mais baixa da solução.

Que outros problemas de gráfico exibem essa troca entre espaço e aproximação?

Estou interessado no caso de gráficos estáticos e dinâmicos, ponderados e não ponderados, não direcionados e direcionados.

Obrigado.

ds.algorithms graph-theory approximation-algorithms space-complexity Rachit
fonte
O trade-off geralmente significa um limite inferior: se você diminui uma coisa, a outra precisa ser maior. Deseja um resultado de limite superior (como no seu exemplo) ou um resultado de limite inferior?
Yoshio Okamoto
1
@YoshioOkamoto - Um limite superior pode "alcançar" um trade-off --- um limite superior pode não significar que o trade-off é essencial (que é uma pergunta do limite inferior), mas pode atingir um. Isso está certo? Independentemente disso, estou interessado nos limites inferior e superior.
Rachit 04/03

Respostas:

-2

esta pesquisa parece ser ativa em um sentido mais aplicado do que o teórico mencionado (isto é, oráculos etc.) com algoritmos de "fluxo de dados" que tentam trabalhar com dados muito grandes através de "janelas deslizantes", com muitos algoritmos gráficos considerados, mas é de fato relativamente novo / recente, se encaixando nas instruções de pesquisa do "big data" .

Nós criamos vários algoritmos para problemas fundamentais de gráficos no modelo W-Stream, incluindo componentes conectados, árvore de abrangência mínima, componentes com biconetação e caminhos mais curtos de fonte única. De acordo com o nosso conhecimento, nossos algoritmos são os primeiros a permitir trocas efetivas de espaço / passes para esses problemas em uma configuração de fluxo de dados.

essa referência inclui outras referências / pesquisas que podem ser úteis.

Apesar das pesadas restrições impostas pelo modelo [streaming clássico], foi alcançado grande sucesso em vários problemas de desenho e estatística de dados, para os quais um número constante de passes e memória de trabalho polilogarítmica foram comprovados o suficiente para encontrar soluções aproximadas (consulte [4, 16, 17] e as extensas bibliografias em [7, 29]).

Além disso:

vzn
fonte