# 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... 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. 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). Apr 2 '16 at 1:52

## 1 Answer

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") runtime of a version of the Simplex algorithm by a polynomial, though the degree of the polynomial is not stated there.

• Thanks. I think Spielman and Teng's smooth analysis shows that if you add some perturbation to the worst-case scenario, you can get a LP problem that Simplex runs in polynomial time. But I was wondering if there are exact characterization of the order of the polynomial for the expected number of pivots. Apr 5 '16 at 17:37
• If you don't perturb by random noise, what's your source of randomness for the "expected number" of pivots? Apr 5 '16 at 19:06
• 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. Apr 7 '16 at 20:17
• I would think that such a setting is even more favorable than an arbitrarily chosen (and then perturbed) linear program... Apr 7 '16 at 20:19
• I agree! Since this is more structured problem, I was thinking that maybe it is possible to use tools from stochastic geometry to derive some nicer results. Apr 7 '16 at 20:22