Samir Khuller wins ESA Test of Time Award

On December 14, 2015, Professor Dorothea Wagner, Steering Committee Chair of the European Symposia for Algorithms (ESA), announced that a Test of Time Award will be given to “Approximation Algorithms for Connected Dominating Sets,” a paper co-authored in 1996 by Professor Samir Khuller, Elizabeth Stevinson Iribe Chair of Computer Science, and Professor Sudipto Guha of the University of Pennsylvania.  The ESA Test of Time Award identifies and celebrates “outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago, and which are still influential and stimulating for the field today.” These award-winning papers have significant citation records, and are still widely used in the field. 

This year, the ESA committee gave awards to two papers, one published in Proceedings between the years 1993-1995, and one published between the years 1994-1996.   Jan van Leeuwen, Kurt Mehlhorn and Mike Paterson comprised this year’s award committee.  Of Guha's and Khuller's work, the committee writes:

“It is natural to require connectedness as an additional constraint for a dominating set, for example, in ad hoc wireless networks. Domination guarantees coverage and connectedness guarantees communication between the selected nodes. Guha and Khuller gave polynomial algorithms for a logarithmic-factor approximation to its solution. Under the usual assumptions, this is the best possible. Their much-cited work has stimulated similar research for connected variants of many other graph problems.”

Guha's and Khuller's paper has been cited hundreds of times in publications ranging from Theoretical Computer Science to IEEE Transactions on Parallel and Distributed Systems to the Journal of Combinatorial Optimization. Their work has widespread application and appeal among a variety of research areas in Computer Science.  

Guha enjoyed the work that he did with Khuller as a graduate student, and had this to say about the award and working with Professor Khuller:

"I am delighted to receive this award with Samir -- I could not be sharing this award with a more wonderful person! I was a graduate student at UMD in 95-96 and this was our first paper together and my first paper ever! This paper was my introduction to approximation algorithms.  I moved on to Stanford to finish my PhD but kept collaborating with Samir. Another body of work with Samir introduced me to facility location problems and eventually my dissertation was on Approximation Algorithms for Facility Location Problems. I have very fond memories of my time at UMD doing this research in the nearby coffee shops and the Dairy!"