An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm

Leta₁ ...,a_m be i.i.d. points uniformly on the unit sphere in ⁿ,m n 3, and letX:= {x ⁿ|a_i^Tx1} be the random polyhedron generated bya₁, ...,a_m. Furthermore, for linearly independent vectorsu, in ⁿ, letS_u, (X) be the number of shadow vertices ofX inspan(u,). The paper provides an asymptotic expansion of the expectation value¯S_n,m:=_in4¹E(S_u,) for fixedn andm .¯S_n,m equals the expected number of pivot steps that the shadow vertex algorithm — a parametric variant of the simplex algorithm — requires in order to solve linear programming problems of type max u^T,xX, if the algorithm will be started with anX-vertex solving the problem max ^T,x X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.