Unlocking a Secret to Business Efficiency
Computer scientist lands top honor for decoding a widely used algorithm
| From Commonwealth | By Caleb Daniloff
Shang-Hua Teng
Until Shang-Hua Teng started college in 1981, after the end of the Great Cultural Revolution, the native of China hadn’t even heard of television, let alone a computer. “I was good with an abacus,” he says.
Now, more than twenty-five years later, Teng has won one of computer science’s top honors. At a conference in Iceland this summer, the College of Arts and Sciences professor of computer science will collect the Gödel Prize, a $5,000 award that recognizes outstanding papers in theoretical science over the past fourteen years. The award is given by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory.
Teng and longtime friend and collaborator Daniel Spielman, a Yale University professor of applied mathematics and computer science, were recognized for their 2004 paper “Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time” in the Journal of the Association of Computing Machinery. In it, they explain why a common algorithm, used to solve efficiency problems everywhere from airlines to online games, functions so well, especially in business.
“Kurt Gödel was one of the great mathematicians, as well as a pioneer of computation,” Teng says. “To win a prize in honor of him is unbelievable.”
The simplex algorithm, developed by George Dantzig in 1947, has practical application in almost all areas of business, including advertising, distribution, pricing, production planning, and transportation, among others. Dantzig’s algorithm has also been successfully applied to diet design, resource conservation, and economic growth prediction.
Stan Sclaroff, chair of the CAS computer science department, says the simplex method is designed to find a solution in a reasonable amount of computing time and behaves very well in practice. But on paper, scientists were able to contrive worst-case scenarios by introducing abnormalities that would cause the algorithm’s behavior to be “horrifyingly bad.”
“For these problem configurations, its running time grows exponentially in the number of constraints to satisfy, and thus it could take virtually forever to find the problem solution,” Sclaroff says. “Smoothed analysis gave an explanation for why the simplex method behaves very well in practice despite the menace of its worst-case complexity. Explaining this behavior had been an open problem since the simplex method’s inception.”
Teng and Spielman began collaborating on improving the simplex method in 1996. Over the years their research changed direction, and in 2004 they published their seminal explanation paper. The National Science Foundation cited the pair’s research in its fiscal year 2003 budget request to Congress as one of the three significant accomplishments funded by its computer science division.
Since joining the BU faculty in 2002, Teng has taught undergraduate and graduate classes in geometric algorithms, cryptography, and computational geometry. He will teach a new course this fall in computational game theory. “Computer game theory is a hot area at the juncture of economics and computer science, where Shang-Hua and his collaborators are answering important open questions,” Sclaroff says. “Stay tuned.”
Download: 
Print: 
Share:
Email: 
Twitter
Facebook
Post Your Comment