Citation:
Haimovich, Mordecai . “Simplex Algorithm Is Very Good!: On The Expected Number Of Pivot Steps And Related Properties Of Random Linear Programs, The”. Discussion Papers 1996. Web.
Abstract:
In their paper How Good is the Simplex Algorithm?, Klee and Minty exhibited a sequence of linear programs for which the number of pivot steps in the simplex algorithm grows exponentially with the dimensions of the program. We present a probabilistic model in which the expected numberof steps for a variant of the simplex method grows linearly with the dimensions. For programs with parallel pair of inequalities (lower and upper bounds), we present a model in which the expected number of steps from minimum to maximum is d. We also present related results concerning the expected complexity of multi-objective linear programming.