Datum / čas
Date(s) - 26.10.
15:00 - 17:00
Kategorie ne Kategorie
Clifford Stein (Columbia University in the City of New York)
Scheduling with Speed Predictions
October 26, 2022 at 15 CET
Join online or offline on our Youtube channel:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract:
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. We study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. In this talk, we give an algorithm that simultaneously achieves, for any x < 1, a 1 + x approximation when the predictions are accurate and a 2+ 2/x approximation when the predictions are not accurate. We also study special cases and evaluate our algorithms performance as a function of the error.
Joint work with Eric Balanski, TingTing Ou and Hao-Ting Wei, all at Columbia.
Clifford Stein conducts research in the design and analysis of efficient algorithms and in combinatorial optimization. His research includes both the rigorous mathematical analysis of algorithms and the algorithm engineering needed to design efficient implementations. He is also the co-author of the popular textbook, Introduction to Algorithms, which has sold over 500,000 copies and been translated into more than a dozen languages.
The seminar is organized by Zdeněk Hanzálek (CIIRC CTU in Prague), Michael Pinedo (New York University) and Guohua Wan (Shanghai Jiao Tong).
Find full info and program at https://schedulingseminar.com/.