Smoothed Analysis: Why the Simplex Algorithm Usually Takes Polynomial Time
arxiv.org
arxiv.org
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.
> 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?
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"
Yes, numerical stability is great as a measure.
It was published around 2009 or so, iirc.
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
[2] It's Smale problem number 9. http://en.wikipedia.org/wiki/Smale's_problems