# The Average-case Complexity of Simplex Algorithm

I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did some work in the 80's that says that if we fix $m$, then the average complexity is linear in $n$ when $n$ goes to infinity.

However, by duality theory, $m$ and $n$ are symmetric in LP. Also in the 80's, Adler et al. showed that the expected number of pivots is quadratic in $\min \{ m, n\}$. (See A Simplex Algorithm Whose Average Number of Steps Is Bounded between Two Quadratic Functions of the Smaller Dimension '') And they even showed a quadratic lower bound.

I was wondering if there are any recent development on such average-case analysis.

• Why do you say "non-asymptotic"? These sound pretty asymptotic to me... – Joshua Grochow Apr 1 '16 at 20:58
• For "non-asymptotic" I mean the bound on the expected number of pivots is a bounded by $C{ min \{ m,n\}^d$ for some constant $d$. It would be great if we could have a sharp characterization what $d$ is. – Steve Apr 1 '16 at 21:04
• I'd still very much call that asymptotic (it's just that you want to know the exponent precisely). Usually "non-asymptotic" means something more along the lines of knowing the exact average number of pivots as a function of n and m (and whatever other parameters may be relevant). I suggest removing "non-asymptotic" from the title, as it makes the title seem a little suspect (since asking for truly non-asymptotic bounds on simplex would either be a very stupid question, or an incredibly difficult one unlikely to be answered here). – Joshua Grochow Apr 2 '16 at 1:52

• Thanks! I am looking for some results that computes the expected number of pivots assuming that the data are drawn from a particular distribution. Say i.i.d. standard Gaussian or $N(0,1)$ distribution. This is different from the smooth analysis. – Steve Apr 7 '16 at 20:17