3 ms·

Smoothed analysis is a pretty handy! For those who aren't apriori familiar with it, heres a wee summary. Its been a few years since i've worked in the area, bu

Smoothed analysis is a pretty handy! For those who aren't apriori familiar with it, heres a wee summary. Its been a few years since i've worked in the area, but the facts havent changed in the mean time. Smoothed analysis asks the question: "If I apply some small random noise on the inputs, whats the average/expected runtime of an algorithm on that noised input?". Then to get the "smoothed complexity" you pick the family of inputs that maximize the average runtime of the algorithm. Turns out for many algorithms which have funny "exponential time" corner cases, but are otherwise polynomial time in practice (like the simplex algorithm used in solving linear programs), the smoothed complexity is polynomial! So smoothed complexity gives a nice way of explaining "slow in theory, fast in practice". Its worth noting that smoothed analysis only really makes sense on algorithms where perturbing the input only changes the answer a little bit, so you need some sort of "numerical stability" style property for the underlying algorithm one way or another.

eru 13y ago
Is it proven, yet, that the simplex algorithm has a smoothed polynomial complexity? Last thing I remember, there were still looking for a variant of the simplex that had that property. (The ellipsoid method and inner point methods are already proven to be polynomial, so we do know that linear programming is polynomial.) > Its worth noting that smoothed analysis only really makes sense on algorithms where perturbing the input only changes the answer a little bit, so you need some sort of "numerical stability" style property for the underlying algorithm one way or another. Aren't there discrete alternatives available?
- carterschonwald 13y ago
  1) the linked paper PROVES simplex has polynomial smoothed complexity. So yes, this paper proves it. Interior points etc have polynomial worst case complexity, which is a different notion ;) 2) yes, theres discrete alternatives, but they're not as problem agnostic as "numerical stability"
  - eru 13y ago
    I didn't read the paper, yet. I was relying on my failing memory of university courses. OK, so I guess the open challenge, I remember, was to do what everyone knows should be possible: come up with a version of simplex that chooses clever enough to get polynomial worst case complexity. (Do you know if any probabilistic variants are in the running?) Yes, numerical stability is great as a measure.
    - carterschonwald 13y ago
      yes, Dan has a randomized simplex with polynomial time. I don't remember the details, but the paper (not paywalled) can be found here http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.p... It was published around 2009 or so, iirc.
- anandkulkarni 13y ago
  Yes, Spielman and Teng showed that the shadow-vertex variation of the simplex method has a smoothed polynomial complexity [1]. It's worth noting that while other LP methods are known to be weakly polynomial, the polynomiality depends on the size of the largest coefficient involved in the problem instance rather than on the number of rows and columns of the LP. Finding a purely polynomial algorithm for linear programming or establishing that none exists is a major open question for linear programming, and indeed, for all of mathematics. It's not a Millenium problem, but it's the next best thing [2]. [1] This paper has an even better result, finding a polylogarithmic simplex variant. http://www-personal.umich.edu/~romanv/papers/simplex.pdf http://www-personal.umich.edu/~romanv/papers/simplex.pdf [2] It's Smale problem number 9. http://en.wikipedia.org/wiki/Smale's_problems http://en.wikipedia.org/wiki/Smale's_problems
  - carterschonwald 13y ago
    ooo, nice link on the simplex bound... I'll have to add that to my infinite read pile.

eru 13y ago

Is it proven, yet, that the simplex algorithm has a smoothed polynomial complexity? Last thing I remember, there were still looking for a variant of the simplex that had that property. (The ellipsoid method and inner point methods are already proven to be polynomial, so we do know that linear programming is polynomial.) > Its worth noting that smoothed analysis only really makes sense on algorithms where perturbing the input only changes the answer a little bit, so you need some sort of "numerical stability" style property for the underlying algorithm one way or another. Aren't there discrete alternatives available?

carterschonwald 13y ago
1) the linked paper PROVES simplex has polynomial smoothed complexity. So yes, this paper proves it. Interior points etc have polynomial worst case complexity, which is a different notion ;) 2) yes, theres discrete alternatives, but they're not as problem agnostic as "numerical stability"
- eru 13y ago
  I didn't read the paper, yet. I was relying on my failing memory of university courses. OK, so I guess the open challenge, I remember, was to do what everyone knows should be possible: come up with a version of simplex that chooses clever enough to get polynomial worst case complexity. (Do you know if any probabilistic variants are in the running?) Yes, numerical stability is great as a measure.
  - carterschonwald 13y ago
    yes, Dan has a randomized simplex with polynomial time. I don't remember the details, but the paper (not paywalled) can be found here http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.p... It was published around 2009 or so, iirc.
anandkulkarni 13y ago
Yes, Spielman and Teng showed that the shadow-vertex variation of the simplex method has a smoothed polynomial complexity [1]. It's worth noting that while other LP methods are known to be weakly polynomial, the polynomiality depends on the size of the largest coefficient involved in the problem instance rather than on the number of rows and columns of the LP. Finding a purely polynomial algorithm for linear programming or establishing that none exists is a major open question for linear programming, and indeed, for all of mathematics. It's not a Millenium problem, but it's the next best thing [2]. [1] This paper has an even better result, finding a polylogarithmic simplex variant. http://www-personal.umich.edu/~romanv/papers/simplex.pdf http://www-personal.umich.edu/~romanv/papers/simplex.pdf [2] It's Smale problem number 9. http://en.wikipedia.org/wiki/Smale's_problems http://en.wikipedia.org/wiki/Smale's_problems
- carterschonwald 13y ago
  ooo, nice link on the simplex bound... I'll have to add that to my infinite read pile.