Events

Colloquium

Energy-Efficient Scheduling with Predictions

Speaker: Cliff Stein (Columbia) Professor of IEOR and Computer Science Columbia University Wednesday, March 25, 2026 11:30AM - 1:00PM Lunch at 11:30am in 1307 Talk 12:00-1:00pm in 1327 Location: Yale Institute for Foundations of Data Science & Webcast, 219 Prospect Street, 13th Floor, New Haven, CT 06511 and via Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0da6bab7-3261-4d8b-870d-b3ca0148ce19

Abstract: In energy-efficient scheduling, the operating system controls the speed at which a machine is processing jobs with the dual objectives of minimizing energy consumption and optimizing the quality of service cost of the resulting schedule. Since machine-learned predictions about future requests can often be learned from historical data, a recent line of work on learning-augmented algorithms aims to achieve improved performance guarantees by leveraging predictions.   In this talk, we first consider a general setting for energy-efficient scheduling and provide a flexible learning-augmented algorithmic framework that takes as input an offline and an online algorithm for the desired energy-efficient scheduling problem. We show that, when the prediction error is small, this framework gives improved competitive ratios for many different energy-efficient scheduling problems, including energy minimization with deadlines, while also maintaining a bounded competitive ratio regardless of the prediction error. Then, we empirically demonstrate that this framework achieves an improved performance on real and synthetic datasets.

These results, while being quite general, require extensive predictions about the input.  We next consider whether similar results are possible for the case when you have much lighter-weight predictions: namely predictions about the speed at which the machine will run.  We show how, for the problem of scheduling to minimize energy while meeting deadlines, we are able to achieve similar guarantees using the speed predictions.

This represents joint work with Eric Balkanski, Jingwei Li, Ting-Ting Ou, Noemie Preivier, Hao-Ting Wei, and Cherlin Zhu.

Speaker Bio: Clifford Stein is a Professor of IEOR and of Computer Science at Columbia University. He is also the Associate Director for Research in the Data Science Institute. From 2008-2013, he was chair of the IEOR department. Prior to joining Columbia, he spent 9 years as an Assistant and Associate Professor in the Dartmouth College Department of Computer Science.

His research interests include the design and analysis of algorithms, combinatorial optimization, operations research, network algorithms, scheduling, algorithm engineering and computational biology. Professor Stein has published many influential papers in the leading conferences and journals in his field, and has occupied a variety of editorial positions including the journals ACM Transactions on Algorithms, Mathematical Programming, Journal of Algorithms, SIAM Journal on Discrete Mathematics and Operations Research Letters. His work has been supported by the National Science Foundation and Sloan Foundation. He is a Fellow of the Association for Computing Machinery (ACM). He is the winner of several prestigious awards including an NSF Career Award, an Alfred Sloan Research Fellowship and the Karen Wetterhahn Award for Distinguished Creative or Scholarly Achievement. He is also the co-author of the two textbooks. Introduction to Algorithms, with T. Cormen, C. Leiserson and R. Rivest is currently the best-selling textbook in algorithms and has sold over half a million copies and been translated into 15 languages. Discrete Math for Computer Scientists , with Ken Bogart and Scot Drysdale, is a text book which covers discrete math at an undergraduate level.

Add To: Google Calendar | Outlook | iCal File

• Colloquium