Zbliżenie przestrzeni Kompromis

W swojej pracy odległości około Oracles , Thorup i Zwick wykazały, że dla każdego wykresu ważonej nieukierunkowane, możliwe jest skonstruowanie struktury danych o rozmiarze , które mogą powrócić do -approximate odległość między dowolną parą wierzchołków na wykresie.$O(k n^{1+1/k})$$(2k-1)$

Na podstawowym poziomie konstrukcja ta osiąga kompromis zbliżenia przestrzeni - można zmniejszyć wymagania przestrzenne kosztem niższej „jakości” rozwiązania.

Jakie inne problemy z grafem wykazują taki kompromis między przestrzenią a przybliżeniem?

Interesują mnie zarówno statyczne, jak i dynamiczne, ważone i nieważone, niekierowane i ukierunkowane wykresy.

Dzięki.

badanie to wydaje się być aktywne w sensie bardziej stosowanym niż teoretyczny, o którym wspominałeś (tj. wyroczniach itp.) z algorytmami „strumieniowania danych”, które próbują pracować z bardzo dużymi danymi przez „przesuwane okna”, z uwzględnieniem wielu algorytmów graficznych, ale jest rzeczywiście stosunkowo nowy / aktualny, zgodny z kierunkami badań „dużych zbiorów danych” .

• Algorytmy kompromisów w modelach strumieniowych , Andrea Ribichini, s. 7:

Opracowaliśmy kilka algorytmów dla podstawowych problemów graficznych w modelu W-Stream, w tym połączone komponenty, minimalne drzewo opinające, komponenty podwójnie połączone i najkrótsze ścieżki z jednego źródła. Zgodnie z naszą najlepszą wiedzą, nasze algorytmy jako pierwsze umożliwiają skuteczne kompromisy w zakresie przestrzeni / przepustowości dla takich problemów w ustawieniach przesyłania danych.

ta referencja obejmuje inne referencje / ankiety, które mogą być pomocne.

Pomimo ciężkich ograniczeń narzuconych przez model [klasycznego przesyłania strumieniowego], osiągnięto duży sukces w przypadku kilku problemów związanych ze szkicowaniem danych i statystykami, dla których udowodniono, że stała liczba przejść i polilogarytmiczna pamięć robocza wystarczają do znalezienia przybliżonych rozwiązań (patrz [4, 16, 17] oraz obszerne bibliografie w [7, 29]).

również:

• Wymiana miejsca na przepustki w problemach ze strumieniowaniem wykresów Camil Demetrescu, Irene Finocchi, Andrea Ribichini