Raum-Annäherung-Kompromiss

14

In ihrer Arbeit Approximate Distance Oracles zeigten Thorup und Zwick, dass es möglich ist, für jeden gewichteten ungerichteten Graphen eine Datenstruktur der Größe zu konstruieren , die ein ( 2 k - 1 ) -Näherungswert liefert Abstand zwischen zwei Scheitelpunkten im Diagramm.Ö(kn1+1/k)(2k-1)

Auf einer fundamentalen Ebene erreicht diese Konstruktion einen Raum-Annäherungs-Kompromiss - man kann den Raumbedarf auf Kosten einer geringeren "Qualität" der Lösung reduzieren.

Welche anderen Graphprobleme weisen einen solchen Kompromiss zwischen Raum und Annäherung auf?

Ich interessiere mich sowohl für statische als auch für dynamische, gewichtete und ungewichtete, ungerichtete und gerichtete Graphen.

Vielen Dank.

ds.algorithms graph-theory approximation-algorithms space-complexity Rachit
quelle
Kompromiss bedeutet normalerweise eine Untergrenze: Wenn Sie eine Sache kleiner machen, muss die andere größer sein. Möchten Sie ein Ergebnis für die obere Grenze (wie in Ihrem Beispiel) oder ein Ergebnis für die untere Grenze?
Yoshio Okamoto
1
@YoshioOkamoto - Eine obere Schranke kann einen Kompromiss "erzielen" - eine obere Schranke bedeutet möglicherweise nicht, dass der Kompromiss wesentlich ist (was eine Frage der unteren Schranke ist), aber sie kann einen Kompromiss erzielen. Ist das richtig? Ungeachtet dessen interessiert mich sowohl die Untergrenze als auch die Obergrenze.
Rachit

Antworten:

-2

Diese Forschung scheint in einem eher angewandten Sinne als im theoretischen Sinne (z. B. Orakel usw.) mit "Daten-Streaming" -Algorithmen aktiv zu sein, die versuchen, mit sehr großen Datenmengen über "Schiebefenster" zu arbeiten, wobei jedoch viele Graph-Algorithmen berücksichtigt werden ist in der Tat relativ neu / neu und passt in die Forschungsrichtung "Big Data" .

Wir haben verschiedene Algorithmen für grundlegende Grafikprobleme im W-Stream-Modell entwickelt, darunter verbundene Komponenten, Minimum Spanning Tree, zweifach verbundene Komponenten und kürzeste Wege aus einer Quelle. Nach unserem besten Wissen sind unsere Algorithmen die ersten, die effektive Kompromisse zwischen Speicherplatz und Pässen für solche Probleme in einer Datenstreaming-Umgebung zulassen.

Dieser Verweis enthält andere Verweise / Umfragen, die hilfreich sein könnten.

Trotz der starken Einschränkungen, die durch das [klassische Streaming] -Modell auferlegt wurden, wurden große Erfolge bei mehreren Datenerfassungs- und Statistikproblemen erzielt, für die sich eine konstante Anzahl von Durchläufen und ein polylogarithmisches Arbeitsgedächtnis als ausreichend erwiesen haben, um ungefähre Lösungen zu finden (siehe [4, 16, 17] und die umfangreichen Bibliographien in [7, 29]).

ebenfalls:

vzn
quelle