Capacitated Covering, Scheduling to Minimize Energy and Min Edge Cost Flows - A Natural Convergence

Google Tech Talk January 25, 2013 (more info below) Presented by Samir Khuller. ABSTRACT "Capacitated Covering, Scheduling to Minimize Energy and Min Edge Cost Flows - A Natural Convergence" Traditional scheduling algorithms, especially those involving job scheduling on parallel machines, make the assumption that the machines are always available and try to schedule jobs to minimize specific job related metrics. Since modern data centers consume massive amounts of energy, we consider job scheduling problems that take energy consumption into account, turning machines off, especially during periods of low demand. The ensuing problems relate very closely to classical covering problems such as capacitated set cover, and we discuss several recent results in this regard. Finally we show how to view all of these problems through the common lens of min edge cost flows. This is a survey talk on several papers, some recent, and some not so recent. Speaker Info: Samir Khuller received his M.S and Ph.D from Cornell University in 1989 and 1990, respectively and is currently Professor and Chair of Computer Science at the University of Maryland, College Park. His research interests are in graph algorithms, discrete optimization, and computational geometry and more recently in scheduling and approximation algorithms. 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.