6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Why do you say "non-asymptotic"? These sound pretty asymptotic to me... $\endgroup$
    – Joshua Grochow
    Apr 1, 2016 at 20:58
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Apr 1, 2016 at 21:04
  • 1
    $\begingroup$ 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). $\endgroup$
    – Joshua Grochow
    Apr 2, 2016 at 1:52

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Apr 5, 2016 at 17:37
  • $\begingroup$ If you don't perturb by random noise, what's your source of randomness for the "expected number" of pivots? $\endgroup$
    – Aryeh
    Apr 5, 2016 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Apr 7, 2016 at 20:17
  • $\begingroup$ I would think that such a setting is even more favorable than an arbitrarily chosen (and then perturbed) linear program... $\endgroup$
    – Aryeh
    Apr 7, 2016 at 20:19
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Apr 7, 2016 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.