Sind einige der modernsten Maximum-Flow-Algorithmen praktisch?

30

Für das Problem des maximalen Durchflusses scheint es eine Reihe sehr ausgefeilter Algorithmen zu geben, von denen mindestens einer erst im letzten Jahr entwickelt wurde. Orlins Max. Fließt in O (mn) Zeit oder besser ergibt einen Algorithmus, der in O (VE) läuft.

Auf der anderen Seite sind die Algorithmen, die ich am häufigsten implementiert sehe (ich behaupte nicht, eine erschöpfende Suche durchgeführt zu haben; dies ist nur eine zufällige Beobachtung):

  • Edmonds-Karp: ,O(VE2)
  • Push-Relabel: oder O ( V 3 ) unter Verwendung der FIFO-Scheitelpunktauswahl,O(V2E)O(V3)
  • Dinics Algorithmus: .O(V2E)

Sind die Algorithmen mit besserer asymptotischer Laufzeit für die Problemgrößen in der realen Welt einfach nicht praktikabel? Außerdem sehe ich, dass "Dynamic Trees" an einigen Algorithmen beteiligt sind. Werden diese jemals in der Praxis eingesetzt?

Hinweis: Diese Frage wurde ursprünglich beim Stapelüberlauf hier gestellt , aber mir wurde gesagt, dass sie hier besser passt.

BEARBEITEN : Ich habe eine verwandte Frage zu cs.stackexchange gestellt , insbesondere zu den Algorithmen, die dynamische Bäume (auch als Link-Cut-Bäume bezeichnet) verwenden, die für Personen von Interesse sein können, die dieser Frage folgen.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
quelle
1
Generell ist es ein bisschen anders, ob ein Algorithmus "praktisch" ist oder ob er "implementiert" ist. Im Idealfall veröffentlichen Autoren Implementierungen ihrer eigenen Algorithmen. In diesem Fall wäre es normalerweise "praktisch", sie zu verwenden. Dies ist in der TCS-Literatur oft eher die Ausnahme. aber es ist oft nicht „praktisch“ zu „implementieren“ andere Autoren Algorithmen nur in Pseudo - Code geschrieben Beschreibungen in Papieren gegeben, die zum Teil erheblich sind oder hochkomplexe ... erfolgreiche Implementierung umfasst gute Tests für die Richtigkeit, einen manchmal schwierigen Prozess ...
VZN
3
Andrew Goldberg verfügte aufgrund seiner Push-Relabel-Arbeit über eine sehr gute Codebasis für verschiedene Varianten von Max Flow. Ich habe den Code in der Vergangenheit verwendet und er war sehr sauber. Leider scheint die Seite nicht mehr zu funktionieren.
Suresh Venkat
3
@vzn Mich interessiert, ob sich die Algorithmen überhaupt für die praktische Umsetzung eignen. Es gibt Algorithmen, bei denen dies nicht der Fall ist, und einige Leute haben sich vorgenommen, diese "galaktischen Algorithmen" zu nennen, da sie ein ausgezeichnetes asymptotisches Verhalten aufweisen, aber so viel Aufwand verursachen, dass es derzeit keinen praktischen Gewinn gibt, sie zu implementieren. (Begriffe niedrigerer Ordnung spielen schließlich eine Rolle.) Die Matrixmultiplikation ist das beste Beispiel, an das ich denken kann, wenn die asymptotisch besten Lösungen niemals in der Praxis Verwendung finden. Ich bin gespannt, ob Max Flow eine ähnliche Situation hat.
Rob Lachlan
5
Ob ein Algorithmus "praktisch" ist oder ob er "implementiert" ist, ist ein bisschen anders. - Das ist richtig. Ein Algorithmus kann implementiert werden, ohne praktisch zu sein, aber nicht umgekehrt.
Jeffs
2
Hier ist der Code aus der experimentellen Untersuchung von Minimum Cut-Algorithmen .
Austin Buchanan

Antworten:

22

Ich bin einer der Autoren des oben verlinkten Papiers.

Ich möchte nur erwähnen, dass wir "State-of-the-Art" -Algorithmen (mit öffentlich verfügbaren Implementierungen) verwenden, die für Instanzen mit maximalem Datenfluss, die in der Bildverarbeitung auftreten, eine gute Leistung erbringen.

Ich möchte auch hinzufügen, dass in diesem engen (aber praktischen) Kontext oft die Algorithmen mit schlechten theoretischen Garantien gut abschneiden. Zum Beispiel ist ref [5] aus unserer Arbeit (Boykov-Kolmogorov-Algorithmus) in der Computer-Vision-Community weit verbreitet, hat jedoch keine stark polyzeitgebundene Laufzeit.

Bei Interesse können Sie die Daten unserer Experimente hier abrufen : http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

Der Code wird auch bald verfügbar sein.

Dhruv Batra
quelle
Sehr gut, dass du der Gruppe beigetreten bist! herzlich willkommen! eine Frage zum Artikel [seit dem 1. Fund]. Es wäre sehr interessant, mehr über den Auswahlprozess der in der Veröffentlichung verwendeten Algorithmen zu erfahren - darauf schien es nicht vollständig einzugehen. Vielleicht könnten Sie sich irgendwo "hinter den Kulissen" über die Auswahl der Algorithmen informieren, die weggelassen wurden, warum, welche Herausforderungen es gab, Implementierungen zu erhalten / auszuführen, was Sie für exotischer halten Algorithmen wie die neueste von Orlins und ihre Aussichten auf eine spätere Implementierung usw.!
vzn
7

Es gibt verschiedene Möglichkeiten, diese Frage zu beantworten, aber nicht unbedingt eine Konsensantwort. Im Allgemeinen sind Algorithmen, die implementiert und für den öffentlichen Vertrieb freigegeben wurden, "praktisch". Einige Algorithmen, die entwickelt wurden, aber noch nicht implementiert wurden, sind möglicherweise praktisch, aber "die Jury ist nicht einverstanden". **

Eine gute Strategie für praktische Zwecke ist die Suche nach einer Umfrage. Auch für diejenigen, die sich für praktische Algorithmen interessieren, können Benchmarks mit Daten aus der realen Welt eine hervorragende Richtlinie für das erwartete Verhalten in der realen Welt sein.

Eine Benchmarking-Umfrage kann ausreichend sein, wird sich jedoch auf die Seite praktikabler Algorithmen stellen. Dies ist eine aktuelle, gründliche empirische Analyse von 14 "State-of-the-Art" -Algorithmen für den maximalen Durchfluss, die empirisch im Vergleich zu Instanzen für die Bildverarbeitung verglichen wurden, bei denen der maximale Durchfluss viele Anwendungen hat. "Stand der Technik" bezieht sich auf "implementierte" Algorithmen.

[1] MaxFlow Revisited: Ein empirischer Vergleich von MaxFlow-Algorithmen für Sehprobleme von Verma und Batra, 2012

** Einige theoretische Algorithmen gehören zunehmend zu einer Kategorie in der TCS-Community, die informell als "galaktisch" bezeichnet wird. Leider kennzeichnen TCS-Autoren ihre Algorithmen in dieser Kategorie derzeit nicht direkt selbst, und es gibt keine veröffentlichten oder allgemein akzeptierten Kriterien für "galaktische" Algorithmen, obwohl es in Blogs Hinweise gibt .

Praktikabilität in diesem Sinne ist möglicherweise eine neue Dimension für das theoretische Studium. idealerweise würde es eine Übersicht über Max-Flow-Algorithmen speziell für diese "praktischen" Achsen / Kriterien geben, die zum Zeitpunkt des Schreibens jedoch wahrscheinlich nicht vorhanden sind. Es ist ein in jüngerer Zeit anerkanntes / anerkanntes Konzept in TCS, das noch nicht gründlich formalisiert wurde (im Gegensatz zu z. B. der weit verbreiteten Akzeptanz von P-Algorithmen als "effizient").

vzn
quelle
3
+1. Ich bin nicht sicher, warum dies abgelehnt wurde; Ich lese das Papier, auf das Sie verlinkt haben, und es hat mir sehr geholfen, die praktischen Ansätze zumindest in diesem Problembereich zu untersuchen.
Rob Lachlan
3
Robert Sedgewick sagte kürzlich in einem Vortrag, dass der Algorithmus-Designer, der keine Experimente durchführt, Gefahr läuft, sich in der Abstraktion zu verlieren. Der Vortrag befasst sich mit dem Finden von Pfaden in Diagrammen und hat auch etwas mit maxflow zu tun. Es beantwortet die Frage nicht, könnte aber für jemanden interessant sein.
Juho
5
@Rob, der einzige relevante Teil in dieser Antwort ist ein Link zum Artikel, und die Antwort enthält nicht viele Erklärungen, warum dieser Artikel überhaupt verlinkt ist. Ich würde vermuten, dass das OP den Link von Google gefunden und nicht gelesen hat. Der Rest der Antwort besteht aus einigen allgemeinen Bemerkungen und Kommentaren, in denen die persönliche Sichtweise von OP auf Themen dargelegt wird, für die er kein Experte ist und die hier nicht wirklich relevant sind. Antworten sind keine Blog-Beiträge. Ein Link zu einem relevanten Artikel mag als Kommentar gut sein, gibt aber keine Antwort. Dies ist eine schlechte Antwort, wenn es eine ist. Deshalb habe ich es runtergestimmt.
Kaveh
2
@ Kaveh fair genug. Ich fand, dass das Papier ein nützlicher Indikator dafür ist, was die Leute für praktisch nützliche Algorithmen halten. Ich stimme zu, dass vieles unbeantwortet bleibt.
Rob Lachlan
3
Ich verstehe die Abstimmungen auch nicht. Es gibt keinen Grund zu der Annahme, dass das Poster den verlinkten Artikel NICHT gelesen hat, und er scheint relevant zu sein. Ich kann den Wunsch sehen, nicht zu stimmen, aber nicht zu stimmen.
Suresh Venkat