<p>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.</p>

CC BY-SA 3.0
2016-04-05T17:37:28.377Z
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.
Steve
CC BY-SA 3.0
2016-04-05T19:06:14.003Z
If you don't perturb by random noise, what's your source of randomness for the "expected number" of pivots?
Aryeh
CC BY-SA 3.0
2016-04-07T20:17:16.333Z
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
CC BY-SA 3.0
2016-04-07T20:19:39.907Z
I would think that such a setting is even more favorable than an arbitrarily chosen (and then perturbed) linear program...
Aryeh
CC BY-SA 3.0
2016-04-07T20:22:44.947Z
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.
Steve
CC BY-SA 3.0
2016-04-03T08:09:03.417Z
2016-04-03T08:09:03.417Z
Aryeh
<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-04-01T20:58:27.327Z
Why do you say "non-asymptotic"? These sound pretty asymptotic to me...
Joshua Grochow
CC BY-SA 3.0
2016-04-01T21:04:56.127Z
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
CC BY-SA 3.0
2016-04-02T01:52:43.520Z
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
<cc.complexity-theory><linear-programming><convex-optimization><average-case-complexity><simplex>
The Average-case Complexity of Simplex Algorithm
Steve
# The Average-case Complexity of Simplex Algorithm

(Asked by: username_0 on 2016-04-01)

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.

**Tags:** cc.complexity-theory, linear-programming, convex-optimization, average-case-complexity, simplex

> **Comments:**
> **username_1**: Why do you say "non-asymptotic"? These sound pretty asymptotic to me...  
> **username_0**: 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.  
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2016-04-03. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: If you don't perturb by random noise, what's your source of randomness for the "expected number" of pivots?  
> **username_0**: 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.  
> **username_2**: I would think that such a setting is even more favorable than an arbitrarily chosen (and then perturbed) linear program...  
> **username_0**: 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.  

---

