Professor Dr. Samir Khulle

(University of Maryland)
hosted by Kurt Mehlhorn

"Capacitated Covering, Scheduling to Minimize Energy and Min Edge Cost Flows - a natural convergence"

(Vortrag im Rahmen der "MPI Distinguished Lecture Series" in Kooperation mit dem Fachbereich Informatik)

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.


Time: Wednesday, 24.02.2016, 03:00 pm
Place: MPI-SWS Saarbrücken, Campus E1 5, room 024