Zoom Link: https://zoom.us/j/96807279045?pwd=P1p1V90vE6K94Wyfne8HbH72lqk8jJ.1

Abstract: NP-complete problems abound in every aspect of our daily lives. One approach is to simply deploy heuristics, but for many of these we do not have any idea as to when the heuristic is effective and when it is not. Approximation algorithms have played a major role in the last three decades in developing a foundation for a better understanding of optimization techniques – greedy algorithms, algorithms based on Linear Programming relaxations have paved the way for the design of (in some cases) optimal heuristics. Are these the best ones to use in “typical” instances? Maybe, maybe not. 

In this talk we will focus on two specific areas – one is in the use of greedy algorithms for a basic graph problem called connected dominating set, and the other is in the development of LP based algorithms for a basic scheduling problem in the context of data center scheduling.

About the Speaker: Samir Khuller received his M.S and Ph.D from Cornell University in 1989 and 1990, respectively, under the supervision of Vijay Vazirani. He spent two years as a Research Associate at the University of Maryland, before joining the Computer Science Department in 1992, where he was a Professor for 27 years. He spent several summers at the IBM T. J. Watson Research Center, and also visited the IBM Tokyo Research Lab for several weeks. From 2003 to 2008 he was the Associate Chair for Graduate Education. and he was the first Elizabeth Stevinson Iribe Chair for CS. As chair he led the development of the Brendan Iribe Center for Computer Science and Innovation, a project completed in March 2019. In March 2019, Khuller joined Northwestern University as the Peter and Adrienne Barris Chair for CS. His research interests are in graph algorithms, discrete optimization, and computational geometry. He has published about 200 journal and conference papers, and several book chapters on these topics. He was an editor for the journal Algorithmica, and International Journal on Foundations of Computer Science, problems Editor for ACM Trans. on Algorithms, and currently is a columnist for SIGACT News and Associate Editor for Networks. He has served on several program committees including SODA 1997, APPROX 1999, APPROX 2000 (chair), STOC 2003, PODS 2006, SODA 2007, APPROX 2010, ESA 2010, STOC 2013, SPAA 2017 and SODA 2021. He served on the ESA Steering Committee from 2012-2016 and chaired the 2019 MAPSP Scheduling Workshop. From 2018-2021 he will serve as the Chair of SIGACT. In 2020, he received the CRA-E Undergraduate Research Mentoring Award.

He received the National Science Foundation's Career Development Award, several Dept. Teaching Awards, the Dean's Teaching Excellence Award and also a CTE-Lilly Teaching Fellowship. In 2003, he and his students were awarded the "Best newcomer paper" award for the ACM PODS Conference. He received the University of Maryland's Distinguished Scholar Teacher Award in 2007, as well as a Google Research Award and an Amazon Research Award. In 2016, he received the European Symposium on Algorithms inaugural Test of Time Award for his work with Sudipto Guha on Connected Dominating Sets. He graduated at the top of the Computer Science Class from IIT-Kanpur.

We look forward to your active participation.