BU Prof Unlocks a Business Algorithm

Until Shanghua 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 25 years later, Teng, a professor of computer science in the College of Arts and Sciences, will travel to Reykjavik, Iceland, for the International Colloquium on Automata, Languages, and Programming (ICALP) to collect one of computer science’s top prizes. The Gödel Prize is a $5,000 award given by the Association for Computing Machinery’s Special Interest Group on Algorithms and Computing Theory and the European Association for Theoretical Computer Science for outstanding papers in theoretical science in the past 14 years. Teng and longtime friend and collaborator Daniel Spielman, a professor of applied mathematics and computer science at Yale University, were recognized for their 2004 paper in the Journal of the Association of Computing Machinery titled “Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time.” 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, the 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’s and Spielman’s work also represents an advance in predicting the performance of algorithms as well as heuristics, which are methods of solving problems through intelligent trial and error. Understanding the mathematical structure of these problems is necessary to designing efficient algorithms and software.

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 FY03 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 next fall in computational game theory. “Computer game theory is a hot area at the juncture of economics and computer science, where Shanghua and his collaborators are answering important open questions,” Sclaroff says. “Stay tuned.”

Caleb Daniloff can be reached at cdanilof@bu.edu.