A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps (Q1100853)

The authors consider a linear program with m inequality constraints and d variables. Assuming a fairly general probabilistic distribution of the problem data they obtain the result that a variant of a simplex method, the parametric constraint-by-constraint algorithm, requires on the average at most 2(min(m,d)1) 2 pivots to solve the problem.