Clustering for faster network simplex pivots

We show how to use a combination of tree-clustering techniques and computat ional geometry to improve the time bounds for optimal pivot selection in th e primal network simplex algorithm for minimum-cost flow and related proble ms and for pivot execution in the dual network simplex algorithm, from O(m) to O(root m) per pivot. Our techniques can also speed up network simplex a lgorithms for generalized flow, shortest paths with negative edges, maximum flow, the assignment problem, and the transshipment problem. (C) 2000 John Wiley & Sons, Inc.