Network simplex algorithm

Network Simplex Algorithm is a graph theoretic specialization of the Simplex algorithm. The algorithm is usually formulated in terms of a standard problem, Minimum-cost flow problem and can be efficiently solved in polynomial time.

History

For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient in practice versions were available. In 1997 Orlin provided the first such algorithm with runtime of $O(V^{2}E\log(VC)$ where $C$ is maximum cost of any edges. Later Tarjan et al improved this to $O(VE\log(V)\log(VC)$.