On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm

Excellent practical perfomance, which led to Dantzig and Hirsch’s linearity conjectures on the one hand, and exponential worst-case behaviour on the other hand are the main benchmarks in complexity analysis of most variants of the simplex algorithm. Borgwardt (1982a,b) was the first to explain this embarrasing gap by means of probabilistic analysis. Using a stochastic problem simulation he proved that the number of pivot steps required by a variant of Gass and Saaty’s parametric objective function algorithm —the “Schatteneckenalgorithmus (shadow vertex algorithm)”—is expected to be polynomial. But knowledge about the average complexity alone does not reveal the algorithm’s properties completely. Important questions remain open. What is the probability of exponential examples? What is the probability of deviations from the mean? So, many researchers, e.g. Shamir (1987) in his survey paper, asked for higher moments or even for the distribution of the random variable “number of pivots”. We are going to derive some information on the variance in this paper.