(Colloquia from 3:30 - 4:30 p.m. in SH 140 with reception to follow in MLH 3)

Speaker: Samir Khuller, Ph.D., Peter and Adrienne Barris Chair of Computer Science, Northwestern University, Evanston, Illinois

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.

Bio
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. 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 served on the ESA Steering Committee from 2012-2016 and chaired the 2019 MAPSP Scheduling Workshop. He received the Best Newcomer paper award from ACM Principles of Database Systems, as well as the inaugural 2016 European Symp. on Algorithms Test of Time Award. He received research awards from Adobe, Dolby, Amazon and Google. From 2018-2021 he served as the Chair of SIGACT. In 2020, he received the CRA-E Undergraduate Research Mentoring Award. He is a Fellow of the ACM and EATCS. In 2023, he joined the (elected) board of the Computing Research Association (CRA). He helped launch the IDEAL Research Institute in 2019.