Select your localized edition:

Close ×

More Ways to Connect

Discover one of our 28 local entrepreneurial communities »

Be the first to know as we launch in new countries and markets around the globe.

Interested in bringing MIT Technology Review to your local market?

MIT Technology ReviewMIT Technology Review - logo

 

Unsupported browser: Your browser does not meet modern web standards. See how it scores »

Finally Answering Why

The result of all this research was the answer to the simple question “Why?” Spielman and Teng finally figured out why the simplex method has worked so well all this time. They did it by developing a new way to analyze the algorithm.

Until their discovery, most mathematicians measured algorithms by using “worst-case analysis,” in which an algorithm is given the most difficult data and then judged on how well it can calculate with it. It would be as if someone handed you the worst possible long-division problem you could imagine and then tested to see whether you could solve it and how long it would take. But this just didn’t work with the simplex method.

So Spielman and Teng found a new approach. They introduced some variability into worst-case analysis. Instead of using exact numbers as inputs to test the algorithm, they allowed imprecision. For example, if the input was 1.31, they allowed a random input between 1.29 and 1.33. They discovered that by allowing for imprecision, the simplex algorithm always efficiently solved the problem, and that is why it has been so successful.

The idea sounds simple, but the mathematics that support it are complex. Spielman and Teng’s first journal paper on the subject, now under review by the Association for Computing Machinery’s Journal of the ACM, contains 80 pages of equations. “I don’t know if that many people could walk through the paper,” Spielman says. In fact, writing the paper even confused Spielman and Teng on occasion. “A couple of times we just threw out what was written and wrote afresh, because if it was complicated for us, it was going to be even more complicated for [other] people,” says Spielman.

Spielman and Teng have presented their findings around the world to enthusiastic response. They published a conference paper in 2001, and since then, both have given invited presentations and keynote addresses throughout the United States and in China, Turkey, Italy, Switzerland, and Denmark.

“This smoothed analysis is an important development,” says Michel Goemans, PhD ‘90, an MIT professor of applied mathematics. And David Johnson, head of the Algorithms and Optimization Department at AT&T Labs-Research, says, “[Smoothed analysis] provides an extra level of confidence for those who use the simplex method.”

Spielman says he hasn’t pulled out his whiteboard since last summer, when the journal paper was finally finished, “but without it, we never would have managed to write the paper.” Now, Spielman recommends that young researchers buy big whiteboards as a good first step toward making breakthroughs. However, Teng attributes a big part of their success to Spielman’s “dynamic” mind and “great taste” in choosing research problems. “He always has the courage to work on the hardest open problem in the field,” Teng says, and that might be an even better starting point for researchers and curious people everywhere.

0 comments about this story. Start the discussion »

Tagged: Business

Reprints and Permissions | Send feedback to the editor

From the Archives

Close

Introducing MIT Technology Review Insider.

Already a Magazine subscriber?

You're automatically an Insider. It's easy to activate or upgrade your account.

Activate Your Account

Become an Insider

It's the new way to subscribe. Get even more of the tech news, research, and discoveries you crave.

Sign Up

Learn More

Find out why MIT Technology Review Insider is for you and explore your options.

Show Me