Compensación de aproximación al espacio

14

En su trabajo , Oráculos de distancia aproximada , Thorup y Zwick demostraron que para cualquier gráfico ponderado no dirigido, es posible construir una estructura de datos de tamaño que pueda devolver una distancia aproximada entre cualquier par de vértices en el gráfico.O(knorte1+1/ /k)(2k-1)

En un nivel fundamental, esta construcción logra una compensación de aproximación de espacio --- se puede reducir los requisitos de espacio a costa de una "calidad" más baja de la solución.

¿Qué otros problemas de gráficos exhiben tal compensación entre espacio y aproximación?

Estoy interesado en el caso de gráficos estáticos y dinámicos, ponderados y no ponderados, no dirigidos y dirigidos.

Gracias.

ds.algorithms graph-theory approximation-algorithms space-complexity Rachit
fuente
El intercambio generalmente significa un límite inferior: si hace que una cosa sea más pequeña, entonces la otra debe ser más grande. ¿Desea un resultado de límite superior (como en su ejemplo) o un resultado de límite inferior?
Yoshio Okamoto
1
@YoshioOkamoto: un límite superior puede "lograr" una compensación --- un límite superior puede no significar que la compensación es esencial (que es una pregunta de límite inferior), pero puede lograr una. ¿Está bien? Independientemente de eso, estoy interesado en los límites inferiores y superiores.
Rachit

Respuestas:

-2

Esta investigación parece ser activa en un sentido más aplicado que el teórico que menciona (es decir, oráculos, etc.) con algoritmos de "transmisión de datos" que intentan trabajar con datos muy grandes a través de "ventanas deslizantes", con muchos algoritmos gráficos considerados, pero es, de hecho, relativamente nuevo / reciente, y se ajusta a las direcciones de investigación de "big data" .

Hemos ideado varios algoritmos para problemas de gráficos fundamentales en el modelo W-Stream, incluidos los componentes conectados, el árbol de expansión mínimo, los componentes biconnectados y las rutas más cortas de una sola fuente. Hasta donde sabemos, nuestros algoritmos son los primeros en permitir compensaciones efectivas de espacio / pases para tales problemas en una configuración de transmisión de datos.

esta referencia incluye otras referencias / encuestas que pueden ser útiles.

A pesar de las fuertes restricciones impuestas por el modelo [de transmisión clásica], se ha logrado un gran éxito para varios problemas de esbozo de datos y estadísticas, para los cuales se ha probado un número constante de pases y memoria de trabajo polilogarítmica para encontrar soluciones aproximadas (ver [4, 16, 17] y las extensas bibliografías en [7, 29]).

además:

vzn
fuente