The Tepper School’s R. Ravi and Brown University Co-Authors Receive Distinguished Test of Time Award

The Annual ACM Symposium on Theory of Computing (STOC), held since 1969, is considered one of the two most important conferences in the field of theory of computing. This year, a 1991 paper by Brown University Computer Science faculty member Philip Klein and his doctoral advisees R. Ravi (now Andris A. Zoltners Professor of Business and Professor of Operations Research and Computer Science at Carnegie Mellon University) and Ajit Agrawal (founder and current head of AKAconomics, a fintech company) has received the conference's 30-year Test of Time Award.

Their 1991 paper, titled "When trees collide: An approximation algorithm for the generalized Steiner problem on networks," presented the influential AKR algorithm; named after the initials of the three inventors. The algorithm helps create efficient networks at a low cost while meeting specific requirements.

"Working on this award-winning paper jump-started my research career," said Ravi. "It added a new tool to the algorithm design palette."

Ravi added that the primal-dual method it enhanced is squarely in the intersection of optimization, algorithms, and graph theory for which Carnegie Mellon and its prestigious Algorithms, Combinatorics, and Optimization doctoral program are known. I have worked on derivatives of the method over the past three decades and am currently working on one with a doctoral student, he said.

The impact of Ravi's research extends beyond the specific problem addressed in the paper. The AKR algorithm pioneered a methodology that has influenced the design and analysis of various approximation algorithms in different domains. This shaped the landscape of facility location, prize-collecting traveling salesman, and feedback vertex set problems.

"This was a true partnership with my advisees," said Klein, who is currently a Professor of Computer Science at Brown University. "I was very fortunate to collaborate with Ajit and Ravi."

Ravi's current research focuses on applications in discrete application in network design and information dissemination, omnichannel fulfillment, online advertising, and more broadly in mechanism design, and social and information networks. His work has been supported by a National Science Foundation (NSF) Career Award and grants from Google, the NSF, the Office of Naval Research, and the Air Force Office of Scientific Research.