The Simplex Method: A Probabilistic Analysis

For more than 35 years now, George B. Dantzig's Simplex-Method has been the most efficient mathematical tool for solving linear programming problems. It is proba­ bly that mathematical algorithm for which the most computation time on computers is spent. This fact explains the great interest of experts and of the public to understand the method and its efficiency. But there are linear programming problems which will not be solved by a given variant of the Simplex-Method in an acceptable time...