This year's Godel Prize

http://opa.yale.edu/news/article.aspx?id=5937

Anyone know what the significance of this is? I didn't really gather
from the article what they were talking about, or why it was so
important.

In article <01c5f522-ccf9-4e4d-836b-9be98d123f87@c58g2000hsc.googlegroups.com>,
<cplxphil@gmail.com> wrote:
>http://opa.yale.edu/news/article.aspx?id=5937
>
>Anyone know what the significance of this is? I didn't really gather
>from the article what they were talking about, or why it was so
>important.

The first and most famous example of smoothed analysis was Spielman and
Teng's analysis of the simplex algorithm for linear programming. It has
long been known that the simple algorithm, as actually implemented, has
worst-case exponential time, but nevertheless runs about as fast as
polynomial-time interior-point methods in practice. Spielman and Teng
took a giant leap forward in our understanding of this phenomenon by
showing that *any* instance of linear programming can be slightly
perturbed to produce an "easy" case. Thus the chances of randomly
hitting a particularly bad case for the algorithm are very small. This
breakthrough has led to new and improved versions of the simplex algorithm.

The general methodology of smoothed complexity has proved to be fruitful
beyond the one example of the simplex algorithm, which further explains
its importance.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

On Aug 14, 9:57 am, tc...@lsa.umich.edu wrote:
> In article <01c5f522-ccf9-4e4d-836b-9be98d123...@c58g2000hsc.googlegroups.com>,
>
> <cplxp...@gmail.com> wrote:
> >http://opa.yale.edu/news/article.aspx?id=5937
>
> >Anyone know what the significance of this is? I didn't really gather
> >from the article what they were talking about, or why it was so
> >important.
>
> The first and most famous example of smoothed analysis was Spielman and
> Teng's analysis of the simplex algorithm for linear programming. It has
> long been known that the simple algorithm, as actually implemented, has
> worst-case exponential time, but nevertheless runs about as fast as
> polynomial-time interior-point methods in practice. Spielman and Teng
> took a giant leap forward in our understanding of this phenomenon by
> showing that *any* instance of linear programming can be slightly
> perturbed to produce an "easy" case. Thus the chances of randomly
> hitting a particularly bad case for the algorithm are very small. This
> breakthrough has led to new and improved versions of the simplex algorithm.
>
> The general methodology of smoothed complexity has proved to be fruitful
> beyond the one example of the simplex algorithm, which further explains
> its importance.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however great, will
> never exceed four of those miles of which as many thousand separate us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences


Interesting, thanks.