Clustering for faster network simplex pivots
David Eppstein · Networks · 2000
We show how to use a combination of tree-clustering techniques and computational geometry to improve the time bounds for optimal pivot selection in the primal network simplex algorithm for minimum-cost flow and related problems and for pivot execution in the dual network simplex algorithm, from O(m) to \documentclass{article}\pagestyle{empty}\begin{document}$0(\sqrt{m})$\end{document} per pivot. Our techniques can also speed up network simplex algorithms for generalized flow, shortest paths with negative edges, maximum flow, the assignment problem, and the transshipment problem. © 2000 John Wiley & Sons, Inc.