Capacitated Covering, Scheduling to Minimize Energy and Min Edge CostFlows -a natural convergence
Samir Khuller
University of Maryland
MPI-Kolloquium
Dr. Samir Khuller is a Professor and the Elizabeth Iribe Chair in the Department
of Computer Science at University of Maryland. His research interests are in
graph algorithms, discrete optimization, scheduling and computational
geometry. He received the University of Maryland's Distinguished Scholar Teacher
Award 2007, as well as a Google Research Award. Most recently he received the
inaugural ESA Test of Time Award for his work on Connected Dominating Sets (with
Sudipto Guha). He received his M.S. and Ph.D. from Cornell University and his
undergraduate degree from IIT-Kanpur.
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.