Calculando distâncias com aproximação menor que 2 em gráficos gerais?

Dado um gráfico não direcionado ponderado com $m = o(n^2)$ arestas, eu gostaria de calcular distâncias de aproximação inferiores a 2 entre qualquer par de vértices. Obviamente, eu gostaria de usar o espaço subquadrático e o tempo de consulta sublinear.

Estou ciente do resultado de Zwick que usa multiplicação de matrizes, mas estou curioso para saber se algum algoritmo combinatório é conhecido por esse problema?

ds.algorithms graph-algorithms Siddhartha
fonte

Oi @Siddhartha, desculpe se esta é uma pergunta idiota: o resultado de Zwick parece usar espaço quadrático, está correto?

Hsien-Chih Chang,

Além disso, o erro aditivo é permitido?

Hsien-Chih Chang,

@ Hsien-ChihChang 張顯之 - Eu estava interessado nos resultados apenas na aproximação multiplicativa. O caso da aproximação aditiva pode ser interessante por si só - mais fácil para gráficos densos, eu acho. Pode-se usar uma chave inglesa e obter uma aproximação aditiva para gráficos densos o suficiente. Para gráficos esparsos, até onde eu sei, as chaves inglesas não ajudariam.

Siddhartha

G

$G$

n

$n$

m

$m$

1

$1$

2

$2$

Ω (m)

$\Omega(m)$

\log_{2} (\binom{N}{m})

$\log_2 \binom{N}{m}$

N = (\binom{n}{2})

$N=\binom{n}{2}$

\geq m \log_{2} (N / m)

$\geq m \log_2 (N/m)$

Sariel Har-Peled

Obrigado Sariel - pode ser possível derivar um limite inferior , mas estou bem com isso. Tudo o que eu gostaria de ter é espaço subquadrático e tempo de consulta sublinear. Para gráficos com arestas, limite inferior não diz nada para o problema - está certo?

Ω (m)

$\Omega(m)$

m = o (n^{2})

$m = o(n^2)$

Ω (m)

$\Omega(m)$

Siddhartha

Respostas:

Até onde eu sei, não há resultado publicado sobre o cálculo de distâncias de aproximação inferiores a 2 no espaço subquadrático e no tempo de consulta sublinear. Para recuperar distâncias aproximadas rapidamente, consulte os resultados e as referências em "Algoritmos mais rápidos para os caminhos mais curtos aproximados de todos os pares" de Baswana e Kavitha (a versão em diário de seu artigo sobre o FOCS tem uma boa revisão do trabalho relacionado); nenhum deles atinge espaço subquadrático.

Para recuperar distâncias aproximadas de maneira compacta, convém examinar os resultados e as referências nos dois documentos acima. [Como complemento à resposta de Gabor, uma palavra de cautela: tenha cuidado com a noção de escarsidade nos artigos acima - para a aproximação , um gráfico é considerado esparso se , como você provavelmente já sabe]. $2$ $m = o(n^2)$

Como Sariel apontou em um dos comentários acima, um limite inferior natural no espaço para calcular distâncias aproximadas menores que é , ou seja, linear no tamanho do gráfico. Se o tempo de consulta não for limitado, esse limite inferior não poderá ser melhorado (trivialmente, é possível usar o algoritmo de caminho mais curto armazenando apenas o gráfico). Para tempo de consulta constante, conheço dois limites inferiores. Primeiro, Patrascu e Roddity tinham alguns limites inferiores condicionais em seu documento do FOCS 2010, que solicitam uma aproximação menor que . Segundo, Sommer et. al. tinha alguns limites mais baixos para gráficos extremamente esparsos. Não conheço outros limites inferiores (não triviais). $2$ $\Omega(m)$ $2$

Em termos de limites superiores, os resultados dos artigos acima parecem não generalizar para aproximações menores que . Recentemente, fizemos alguns progressos nesse problema. O artigo deverá estar no ArXiv em breve, mas se você quiser, envie-me um e-mail e ficarei feliz em compartilhar o artigo. $2$

Espero que isto ajude.

~ Rachit Agarwal

Rachit
fonte

Você pode estar interessado no documento INFOCOM de Rachit Agarwal 2011:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled Consultas de distância aproximada e roteamento compacto em gráficos esparsos, IEEE INFOCOM 2011

Do resumo:

[Para um] gráfico com grau médio , casos especiais de nossas estruturas de dados recuperam dois caminhos extensos com espaço [...] ao custo de tempo de consulta. $\Theta(\log n)$ $O(n^{3/2})$ $O(\sqrt{n})$

Observe que seu oráculo de distância é apenas para gráficos esparsos, mas o limite logarítmico do grau parece plausível. Adicionado bônus, o algoritmo também funciona para gráficos ponderados.

Gabor Retvari
fonte

Você também pode querer dar uma olhada

Pătraşcu, Roditty, Oráculos a distância além do Thorup - Zwick Bound , FOCS 2010

Eles têm um oráculo de distância do tamanho com o trecho 2. Ele suporta consultas em tempo constante. $O(n^{5/3})$

zotachidil
fonte

Obrigado! O artigo de Agrawal e Mihai parece não dizer nada sobre a aproximação "menor que" 2, a menos que eu tenha perdido alguma coisa.

Siddhartha

Não é, mas pode lhe dar uma idéia sobre como obter uma troca para melhorar o alongamento.

Zotachidil 11/11