Premium
Clustering for faster network simplex pivots
Author(s) -
Eppstein David
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(200005)35:3<173::aid-net1>3.0.co;2-w
Subject(s) - simplex , simplex algorithm , transshipment (information security) , cluster analysis , flow network , minimum cost flow problem , mathematical optimization , maximum flow problem , computer science , selection (genetic algorithm) , algorithm , mathematics , flow (mathematics) , combinatorics , tree (set theory) , linear programming , artificial intelligence , operations research , geometry
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.