Calcular distancias con una aproximación menor que 2 en gráficos generales?

Dado un gráfico ponderado no dirigido con $m = o(n^2)$ aristas, me gustaría calcular distancias de aproximación menores que 2 entre cualquier par de vértices dado. Por supuesto, me gustaría utilizar el espacio subcuadrático y el tiempo de consulta sublineal.

Soy consciente del resultado de Zwick que utiliza la multiplicación de matrices, pero tengo curiosidad por saber si se conocen algoritmos combinatorios para este problema.

ds.algorithms graph-algorithms Siddhartha
fuente

Hola @Siddhartha, lo siento si esta es una pregunta tonta: el resultado de Zwick parece utilizar un espacio cuadrático, ¿es correcto?

Hsien-Chih Chang 張顯之

Además, ¿está permitido el error aditivo?

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之: solo me interesaban los resultados de aproximación multiplicativa. El caso de la aproximación aditiva puede ser interesante por derecho propio, supongo que es más fácil para gráficos densos. Se puede usar una llave inglesa y obtener una aproximación aditiva para gráficos suficientemente densos. Para gráficos dispersos, hasta donde yo sé, las llaves no ayudarían.

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)$

Gracias Sariel: es posible obtener un límite inferior de pero estoy de acuerdo con eso. Todo lo que me gustaría tener es un espacio subcuadrático y un tiempo de consulta sublineal. Para los gráficos con bordes, límite inferior no dice nada para el problema - ¿es correcto?

Ω (m)

$\Omega(m)$

m = o (n^{2})

$m = o(n^2)$

Ω (m)

$\Omega(m)$

Siddhartha

Respuestas:

Hasta donde yo sé, no hay un resultado publicado sobre el cálculo de distancias de aproximación inferiores a 2 en el espacio subcuadrático y el tiempo de consulta sublineal. Para recuperar rápidamente las distancias aproximadas, es posible que desee ver los resultados y las referencias en "Algoritmos más rápidos para rutas más cortas aproximadas de todos los pares" de Baswana y Kavitha (la versión de la revista de su documento FOCS tiene una buena revisión del trabajo relacionado); ninguno de estos logra espacio subcuadratico.

Para recuperar distancias aproximadas de manera compacta, es posible que desee ver los resultados y las referencias en los dos documentos anteriores. [Como una adición a la respuesta de Gabor, una palabra de precaución: tenga cuidado con la noción de escasez en los documentos anteriores; para la aproximación , se dice que un gráfico es escaso si , como usted probablemente ya lo sé]. $2$ $m = o(n^2)$

Como señaló Sariel en uno de los comentarios anteriores, un límite inferior natural en el espacio para calcular distancias de aproximación menores que es , es decir, lineal en el tamaño del gráfico. Si el tiempo de consulta no está limitado, este límite inferior no se puede mejorar (trivialmente, uno puede usar el algoritmo de ruta más corta simplemente almacenando el gráfico). Para el tiempo de consulta constante, sé de dos límites inferiores. Primero, Patrascu y Roddity tenían algunos límites inferiores condicionales en su documento FOCS 2010 que solicitan una aproximación menor a . En segundo lugar, Sommer et. Alabama. tenía algunos límites inferiores para gráficos extremadamente escasos. No conozco ningún otro límite inferior (no trivial). $2$ $\Omega(m)$ $2$

En términos de límites superiores, los resultados de los documentos anteriores no parecen generalizarse a una aproximación menor que . Recientemente hicimos algunos progresos en este problema. El documento debería estar en ArXiv pronto, pero si lo desea, envíeme un correo electrónico y estaré encantado de compartirlo. $2$

Espero que esto ayude.

~ Rachit Agarwal

Rachit
fuente

Quizás te interese el artículo INFOCOM 2011 de Rachit Agarwal:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled Distancia aproximada Consultas y enrutamiento compacto en gráficos dispersos, IEEE INFOCOM 2011

Del resumen:

[Para un] gráfico con grado medio , los casos especiales de nuestras estructuras de datos recuperan trazados de tramo 2 con espacio [...] a costa de tiempo de consulta. $\Theta(\log n)$ $O(n^{3/2})$ $O(\sqrt{n})$

Tenga en cuenta que su oráculo de distancia es solo para gráficos dispersos, pero el límite de grado logarítmico parece plausible. Bonificación adicional, el algoritmo también funciona para gráficos ponderados.

Gabor Retvari
fuente

También es posible que desee echar un vistazo a

Pătraşcu, Roditty, Oráculos a distancia más allá del Thorup - Zwick Bound , FOCS 2010

Tienen un oráculo de distancia de tamaño con estiramiento 2. Admite consultas en tiempo constante. $O(n^{5/3})$

zotachidil
fuente

¡Gracias! El documento de Agrawal y Mihai no parece decir nada sobre la aproximación "menor que" 2, a menos que me haya perdido algo.

Siddhartha

No lo es, pero podría darle una idea sobre cómo obtener una compensación para mejorar el estiramiento.

zotachidil