BU Prof Unlocks a Business Algorithm (the Linear Programming Simplex Algorithm)
Boston University (06/13/08) Daniloff, Caleb
Boston University professor Shanghua Teng and Yale University professor Daniel Spielman will receive ACM's Godel Prize at the International Colloquium on Automata, Languages, and Programming (ICALP), awarded by ACM's Special Interest Group on Algorithms and Computing Theory and the European Association for Theoretical Computer Science. The $5,000 award is given for outstanding papers in theoretical science. Teng and Spielman are being recognized for their 2004 paper in the Journal of the ACM titled "Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time." The paper explains why a common algorithm, used to solve efficiency problems in fields ranging from airlines to online games, functions so well, particularly in business. The simplex algorithm, developed in 1947 by George Dantzig, has practical applications in almost all areas of business, including advertising, distribution, pricing, production planning, and transportation. The simplex algorithm is designed to find a solution in a reasonable amount of time, but scientists have been able to create worst-case scenarios by introducing abnormalities that cause the algorithm's running time to grow exponentially, creating a situation where it could take virtually forever to find a solution. Smoothed analysis gives an explanation for why the simplex method behaves so well in practice despite the danger of its worst-case complexity. Teng's and Spielman's work also represents an advance in predicting the performance of algorithms and heuristics.
Click Here to View Full Article
No comments:
Post a Comment