The Simplex Solution

Continued from page 2

By Megan Vandre

June 2003

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.