Posts

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

The paper (“When trees collide: An approximation algorithm for the generalized Steiner problem on networks”) describes the problem addressed as follows: “Here’s the scenario: You’re in the business of providing communication channels to your customers. You have a set of clients with communication requirements; each client has specified a pair of cities between which the client must have communication capabilities….Your job is to select a minimum-cost collection of communication links that can accommodate all your clients’ communication requirements. The network you must construct need not be connected….” [emphasis added]

Here’s an example with four clients: circle, diamond, pentagon, and square:

One solution is to connect each client’s pair of sites individually: 

A cheaper solution would be to build a single network connecting all sites: 

But in some cases, the cheapest solution would involve identifying clusters of nearby sites and forming a separate network for each cluster: 

What’s more, the two problems, identifying clusters and forming networks, should be solved jointly because the choice of clusters depends on the cost of the resulting networks. It is this problem, jointly identifying clusters and forming networks, that the algorithm (now known as AKR, after the initials of the three inventors) addresses.

Unfortunately, the problem is NP-hard, which means we don’t expect to find an efficient algorithm that’s guaranteed to output the cheapest solution. The paper gives a 2-approximation algorithm, an algorithm guaranteed to output a solution whose cost is at most twice the cheapest but performs much better in practice. 

The significance of the research, however, goes beyond the specific problem addressed. The paper pioneered a methodology that informed the design and analysis of many subsequent approximation algorithms for diverse other problems, with names such as facility location, prize-collecting traveling salesman, and feedback vertex set. According to Michel X. Goemans and David P. Williamson, who were the first to build on the techniques introduced in the paper, the AKR algorithm was “the first highly sophisticated use of the primal-dual method in the design of approximation algorithms”. Through the work of Goemans and Williamson and many other researchers, the methodology employed by the AKR paper has become a fundamental tool for algorithm designers.

“This was a true partnership with my advisees,” says Philip, “and I was very fortunate to collaborate with Ajit and Ravi.”

Philip’s research continues to focus on algorithms for optimization problems in graphs. He’s a Fellow of the Association for Computing Machinery as well as a recipient of the National Science Foundation's Presidential Young Investigator Award and of Brown University's Philip J. Bray Award for Excellence in Teaching in the Sciences. In 2015 and 2016, he was a Fellow at the Radcliffe Institute for Advanced Study at Harvard University. Next semester, he will be in residence at the Simons Institute for Theory of Computing at UC Berkeley. He’s published two textbooks, A Cryptography Primer: Secrets and Promises and Coding the Matrix: Linear Algebra through Applications to Computer Science.

The photo of Philip Klein above is from the era of the award-winning paper. For more information about this news item, click the link that follows to contact Brown CS Communications Manager Jesse C. Polhemus.