IMPROVED ASYMPTOTIC ANALYSIS OF THE AVERAGE NUMBER OF STEPS PERFORMED BY THE SELF-DUAL SIMPLEX ALGORITHM

In this paper we analyze the average number of steps performed by the self-dual simplex algorithm for linear programming, under the probabilistic model of spherical symmetry. Consider a problem of n variables with m constraints. S. Smale established that for every number of constraints m, there is a constant c(m) such that the number of pivot steps of the self-dual algorithm, rho (m,n), is less than c(m)(ln n)**m**(**m** plus **1**). We improve upon this estimate by showing that rho (m,n) is in fact bounded by a function of m only. The symmetry of the function in m and n implies that rho (m,n) is in fact bounded by a function of the smaller of m and n.