Inkrementeller maximaler Durchfluss in dynamischen Diagrammen

Ich suche nach einem schnellen Algorithmus zur Berechnung des maximalen Durchflusses in dynamischen Diagrammen. dh wenn ein Graph $G=(V,E)$ und , haben wir den maximalen Fluss in von nach . Dann wird der neue / alte Knoten mit seinen entsprechenden Kanten hinzugefügt / gelöscht, um einen Graphen . Was ist ein maximaler Durchfluss in einem neu erstellten Diagramm? Gibt es eine Möglichkeit, die Neuberechnung des maximalen Durchflusses zu verhindern?F G s t u G $s,t\in V$$F$$G$$s$$t$$u$$G^1$

Jede Vorverarbeitung, die nicht sehr zeit- und speicherintensiv ist, wird geschätzt.

Die einfachste Idee ist die Neuberechnung des Durchflusses.

Eine weitere einfache Idee ist, alle in der vorherigen Berechnung des maximalen Durchflusses verwendeten Erweiterungspfade abzuspeichern, um einen Scheitelpunkt hinzuzufügen $v$. Wir können einfache Pfade (im aktualisierten Kapazitätsdiagramm nach vorherigem Schritt) finden, die von der Quelle ausgehen, zu der $v$ dann weitergehen zum Ziel, aber das Problem ist, dieser Pfad sollte einfach sein, ich könnte nicht besser als $O(n\cdot m)$ für diesen Fall finden, für $m=|E|$. (Beachten Sie auch, dass dies in erfolgen könnte, wenn es nur ein Pfad wäre, aber das ist nicht der Fall $O(n+m)$.)

Auch zum Entfernen von Knoten über Idee funktioniert nicht.

Ich habe auch schon Papiere wie Inkrementelle Annäherung für Kanten gesehen , aber in diesem Fall scheinen sie nicht gut genug zu sein, es ist mehr als für jede Kante und in diesem Fall scheint es keine geeignete Erweiterung zu sein (wir berechnen nur einen Fluss neu). Derzeit verwende ich auch den Ford-Fulkerson-Algorithmus für maximalen Durchfluss. Wenn es eine bessere Option für Online-Algorithmen gibt, ist es gut, dies zu wissen.$O(m)$

Der beschriebene Ansatz ist möglicherweise theoretisch nicht optimal. Es ist nur eine einfache praktische Lösung, die für den Autor funktionieren kann. Ich kann keine Referenzen nennen, weil ich immer dachte, dass es eine weithin bekannte Folklore ist, aber seltsamerweise hat es niemand in der Antwort gepostet. Also mache ich es.

Angenommen, wir haben ein ungerichtetes Netzwerk . Angenommen, es ist in einer Datenstruktur gespeichert, die ein einfaches Einfügen / Löschen von Scheitelpunkten / Bögen ermöglicht. Manchmal verwenden wir das Restnetz G f (dh mit aktualisierten Kapazitäten c f = c - f ).$G=(V,E,c)$$G_f$$c_f = c - f$

Im ersten Teil wird das Einfügen / Löschen von Scheitelpunkten behandelt. Es ist mehr oder weniger einfach für Einfügungen:

1. Fügen Sie dem verbleibenden Netzwerk einen neuen Scheitelpunkt mit entsprechenden Kanten hinzu.
2. Finden Sie mit einem Maxflow-Algorithmus Ihrer Wahl einen maximalen Durchfluss im aktualisierten Restnetzwerk.

Bei Löschungen wurden die Dinge komplizierter. Stellen Sie sich vor wir den Scheitelpunkt geteilt wir sind in 2 Hälften löschen v i n und v o u t , so dass alle in-Bögen Punkte v i n , alle out-Bögen aus geht v o u t und dieses neue Eckpunkte verbunden sind durch einen Bogen von unendlicher Kapazität. Dann ist das Löschen von v gleichbedeutend mit dem Löschen des Bogens zwischen v i n und v o u t . Was wird in diesem Fall passieren? Lassen Sie uns mit f $v$$v_{in}$$v_{out}$$v_{in}$$v_{out}$$v$$v_{in}$$v_{out}$$f^v$die Strömung durch den Scheitelpunkt . Dann v i n überschüssige Erfahrung f v Durchflußeinheiten und v o u t Mangel erfahren wird f v Durchflußeinheiten rechts nach dem Löschen (die Strömungsbeschränkungen offensichtlich aufgebrochen werden). Um die Flussbeschränkungen wieder aufrechtzuerhalten, sollten wir die Flüsse neu ordnen, aber auch den ursprünglichen Flusswert so hoch wie möglich halten. Lassen Sie uns zuerst sehen, ob wir eine Umlagerung durchführen können, ohne den Gesamtfluss zu verringern. Um dies zu überprüfen, finden Sie einen maxflow ~ f v von v i n bis v o $v$$v_{in}$$f^v$$v_{out}$$f^v$$\tilde{f^v}$$v_{in}$ im "abgeschnittenen" Restnetz (dh ohne die Verbindung von v i n und v o u t ). Wir sollten esoffensichtlich f v binden. Wenn es zufällig gleich f v ist, haben wir Glück: Wir haben den Fluss, der durchv lief,soneu zugewiesen, dass der Gesamtfluss nicht geändert wurde. Im anderen Fall muss der Gesamtdurchfluss um einen "nutzlosen" Überschuss vonΔ= f v - ~ f v Einheitenverringert werden. Verbinden Sie dazu vorübergehendsund$v_{out}$$v_{in}$$v_{out}$$f^v$$f^v$$v$$\Delta = f^v - \tilde{f^v}$$s$$t$durch einen Bogen mit unendlicher Kapazität und führe den Maxflow-Algorithmus erneut von zu v o u t aus (wir sollten den Flow durch Δ begrenzen ). Dadurch wird das verbleibende Netzwerk repariert und die Durchflussbeschränkungen werden wieder aufrechterhalten, wodurch der Gesamtdurchfluss automatisch um Δ verringert wird .$v_{in}$$v_{out}$$\Delta$$\Delta$

Die zeitliche Komplexität solcher Aktualisierungen kann vom verwendeten maxflow-Algorithmus abhängen. Die schlimmsten Fälle mögen zwar ziemlich schlimm sein, aber es ist immer noch besser als eine vollständige Neuberechnung.

Der zweite Teil ist der zu verwendende Maxflow-Algorithmus. Soweit ich weiß, benötigt der Autor keinen sehr komplexen (aber immer noch effizienten) Algorithmus mit einer kleinen versteckten Konstante, um ihn auf einer mobilen Plattform auszuführen. Seine erste Wahl für Ford-Fulkerson (ich gehe davon aus, dass es sich um Edmonds-Karp handelt ) sieht aus dieser Sicht nicht schlecht aus. Es gibt aber auch einige andere Möglichkeiten. Die erste Variante, die ich empfehlen würde, ist die Variante des Dinic-Algorithmus, da sie in der Praxis recht schnell ist und auf sehr einfache Weise implementiert werden kann. Andere Optionen können die Kapazitätsskalierung von Ford-Fulkerson in O ( | E $O(|V|^2|E|)$ und schließlich verschiedene Versionen von Push-Relabel mit Heuristik. In jedem Fall hängt die Leistung von einem Anwendungsfall ab, sodass der Autor den besten empirisch finden sollte.$O(|E|^2 \log C_{max})$

ok unter berücksichtigung neuer infos und vermeidung einiger kniffliger falscher start / red herring refs (mea culpa), hier sind einige neue refs dazu.

Schnelle Lösung einer Online-Sequenz von Problemen mit maximalem Durchfluss mit Erweiterungen für die Berechnung robuster Minimalschnitte Doug Altner und Özlem Ergun

Dieser Verweis berücksichtigt Online- Sequenzen von MFPs und "Warmstarts", dh aufbauend auf inkrementellen Chgs zu einem früheren MFP. "Wir zeigen, dass unsere Algorithmen die Laufzeit im Vergleich zu ähnlichen Codes, die einen Black-Box-MFP-Solver verwenden, um eine Größenordnung verkürzen. Insbesondere zeigen wir, dass unser Algorithmus für robuste Minimalschnitte Instanzen in Sekunden lösen kann, die über vier benötigen würden Stunden mit einem Black-Box-Maximum-Flow-Solver. "

Fortschritte bei Problemen mit maximalen Durchflussmengen Altner, Douglas S., Georgia Tech

In dieser Dissertation von 2008 (PDF zum Herunterladen) geht der Autor auf das Problem des inkrementellen Hinzufügens von Bögen ein, das dem Problem des Hinzufügens neuer Scheitelpunkte (mit mehreren neuen Bögen) "nahe genug" zu sein scheint.

Ein Großteil dieses Verweises befasst sich mit dem Löschen von Teilen des Netzwerks (Kürzungen / "Verbot"), wie im ersten Teil des Abstracts angegeben

siehe esp "IV ONLINE-ABLAUF VON MAXIMALEN DURCHFLÜSSEN LÖSEN.... S63".

"Das Ziel dieses Kapitels ist es jedoch, den Leser davon zu überzeugen, dass die iterative Verwendung eines Black-Box-Maximum-Flow-Lösers zur Lösung einer großen Sequenz von MFPs zu einer enormen Anzahl unnötiger Berechnungen führen kann."

p66 In den oben genannten Anwendungen sind die MFPs typischerweise topologisch ähnlich. Das heißt, das nächste MFP in der Sequenz unterscheidet sich vom vorherigen durch Hinzufügen oder Entfernen einer kleinen Anzahl von Lichtbögen oder durch vorhersagbare Änderung der Kapazität eines lokalisierten Lichtbogensatzes Wenn diese Instanzen gelöst werden, ist die Zeit und der Raum, die erforderlich sind, um irgendetwas zu speichern, das über die Lösung des vorherigen Problems hinausgeht, in der Regel nicht gerechtfertigt. "

Der Autor von p67 verwendet auch hier den "Warmstart" -Ansatz. "Eine effektive Strategie zur schnellen Lösung einer gesamten Online-Sequenz von Optimierungsproblemen ist die Entwicklung effizienter Heuristiken für die Neuoptimierung. Zu diesem Zweck entwickeln wir einen modifizierten Maximalflussalgorithmus, der für einen effizienten Warmstart ausgelegt ist."

Siehe insbesondere Seite 71, die das spezifische inkrementelle New-Arc-Problem aufweist:

New Arc Maximum Flow Reoptimization Problem (NAMFRP)

der autor betrachtet die allgemeineren probleme p67

Problem der erneuten Optimierung des
maximalen Durchflusses (MFROP) Problem der erneuten Optimierung des maximalen Durchflusses durch einen einzelnen Lichtbogen (MFSAROP)

Aus einer kurzen Suche geht hervor, dass die Online-Version ein Bereich aktiver Forschung ist. Sie erwähnen nicht den Anwendungsbereich, der dazu beitragen könnte, die Literatursuche einzugrenzen. Eine Möglichkeit besteht darin, nach einem Anwendungsbereich zu suchen, in dem es die meisten oder neuesten Innovationen gibt. Daher gibt es eine gewisse Anwendung des inkrementellen maximalen Durchflusses in Bildverarbeitungssystemen und einige Algorithmen dafür. Probieren Sie Maximum Flows by Incremental Breadth-First Search in Microsoft Research Labs. Wenn man das Intro zu diesem Artikel paraphrasiert, ist der Boykov- und Kolmogorov-Algorithmus anscheinend für Sehinstanzen gut geeignet und es sind keine exponentiellen Zeitgegenbeispiele bekannt, obwohl er außerhalb der Sehanwendungen möglicherweise eine schlechte Leistung erbringt. Es könnte sich also lohnen, den B & K-Algorithmus für Ihre Daten auszuprobieren und zu sehen, wie er funktioniert.

Sie scheinen zu sagen, dass ein inkrementeller Algorithmus, der in der Anzahl der Graphenkanten linear ist, nicht ausreicht? Aber ist das nicht ein ziemlich hoher Wirkungsgrad? Mit wie vielen Kanten haben Sie es zu tun? Möglicherweise besteht der Ansatz darin, die Kosten für das Durchlaufen des Diagramms zu senken, wenn dies teuer oder ein wesentlicher Faktor ist (z. B. in db gespeichertes Diagramm im Vergleich zum im Speicher gespeicherten Diagramm).

Hier ist eine interessante Arbeit, die argumentiert, dass, während der nicht inkrementelle Algorithmus für den maximalen Durchfluss in P ist, die inkrementelle Version NP vollständig ist. "Nach unserem besten Wissen sind unsere Ergebnisse die ersten, die ein P-Zeit-Problem finden, dessen inkrementelle Version NP-vollständig ist."

Inkrementeller Durchfluss von Hartline, Sharp

Eine weitere Möglichkeit / Richtung ist der Push-Relabel-Maximalfluss- Algorithmus, der "einer der effizientesten Algorithmen für den Maximalfluss" ist und in Abhängigkeit von Ihren Daten bessere Komplexitätsprofile aufweisen kann. zB wie auf der Wikipedia-Seite steht

$O(V^3)$$O(V^2 \sqrt E$$O(V \cdot E \cdot log(V^2 / E))$