Programming in Networks and Graphs: On the Combinatorial Background and Near-Equivalence of Network Flow and Matching Algorithms (Lecture Notes in Economics & Mathematical Systems) - Softcover

Inhaltsangabe

Netzwerkfluss und Matching werden in der Literatur oft separat behandelt und für jede Klasse wurden verschiedene Algorithmen entwickelt. Diese Algorithmen werden normalerweise als primal, dual, primal-dual usw. klassifiziert. Die Frage, die sich der Autor in dieser Arbeit stellt, ist die Existenz eines gemeinsamen kombinatorischen Prinzips, das all diesen scheinbar unterschiedlichen Ansätzen inhärent sein könnte. Es wird gezeigt, dass alle gängigen Netzwerkfluss- und Matching-Algorithmen implizit dem sogenannten kürzesten Augmenting-Pfad folgen. Dies kann als gierige Entscheidungsregel interpretiert werden, bei der die optimale Lösung durch eine Abfolge lokaler optimaler Lösungen aufgebaut wird. Die Effizienz dieses Ansatzes wird durch die Kombination dieser kurzsichtigen Entscheidungsregel mit einer antizipierenden Organisation realisiert. Der Ansatz dieser Arbeit ist wie folgt organisiert. Für mehrere Standard-Flow- und Matching-Probleme werden zunächst die gängigen Lösungsverfahren überprüft. Es wird dann gezeigt, dass sie sich alle auf ein gemeinsames Grundprinzip reduzieren, das heißt, sie führen alle dieselben Rechenschritte durch, wenn bestimmte Bedingungen richtig eingestellt sind und Bindungen nach einer gemeinsamen Regel unterbrochen werden. In Anbetracht dieser nahezu äquivalenten Äquivalenz aller häufig verwendeten Algorithmen muss die Frage nach der besten Methode geändert werden - alle Methoden sind (nur) verschiedene Implementierungen desselben Algorithmus, die durch unterschiedliche Ansichten des Problems erhalten werden.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.