Motivation für die Entwicklung von Simplex-Algorithmen für kürzeste Wege

Ich lese Efficient Shortest Path Simplex-Algorithmen von Donald Goldfarb, Jianxiu Hao und Shen-Roan Kai, die "die Spezialisierung des Primal Simplex-Algorithmus auf das Problem der Suche nach einem Baum gerichteter kürzester Pfade von einem bestimmten Knoten zu allen anderen Knoten in" betrachteten Ein Netzwerk von n Knoten oder das Finden eines gerichteten Zyklus negativer Länge. Zwei effiziente Varianten dieses Simplex-Algorithmus für den kürzesten Weg werden analysiert und es wird gezeigt, dass sie höchstens Drehpunkte und erfordern Zeit. "$(n − 1)(n − 2)/2$$O(n^3)$

Ich versuche, Motivation für diesen Artikel zu finden und frage mich, ob der Bellman-Ford-Algorithmus nicht gut genug ist. Es funktioniert in -Zeit, was gut für die Art des Graphen ist, mit dem sich das obige Problem befasst.$O(nm)$

Ein großes offenes Problem bei der mathematischen Programmierung ist das Entwerfen eines stark polynomiellen zeitlinearen Programmieralgorithmus. Ein verwandtes Problem ist, ob irgendeine Variante des Simplex-Algorithmus in stark polynomieller Zeit läuft. Es ist sinnvoll, zunächst starke Polynomzeitgrenzen für Simplex-Varianten zu beweisen, die auf Probleme angewendet werden, für die wir bereits wissen, dass starke Polynomzeitalgorithmen existieren.