Sometimes the worst-case scenario can lead to the best-case solution. That's the premise behind Shang-Hua Teng's (CS'91) development of the smooth analysis theory that measures the complexity of algorithms. Teng and his collaborators have proven that some algorithms can still be effective and practical despite being run in the worst possible case scenarios. For his groundbreaking work, Teng has won the 2009 Delbert Ray Fulkerson Prize, a prestigious award given every three years by the Mathematical Programming and American Mathematical Societies.
Camille Downing