Re: This year's Godel Prize
- From: cplxphil@xxxxxxxxx
- Date: Fri, 15 Aug 2008 18:50:47 -0700 (PDT)
On Aug 14, 9:57 am, tc...@xxxxxxxxxxxxx wrote:
In article <01c5f522-ccf9-4e4d-836b-9be98d123...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<cplxp...@xxxxxxxxx> 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.
.
- References:
- This year's Godel Prize
- From: cplxphil
- Re: This year's Godel Prize
- From: tchow
- This year's Godel Prize
- Prev by Date: The Best Online Money Maker Ever
- Next by Date: Decidability of P = NP
- Previous by thread: Re: This year's Godel Prize
- Next by thread: Online Iterated Prisoner's Dilemma
- Index(es):
Relevant Pages
|
