Online Scheduling via Learned Weights
Published in Symposium on Discrete Algorithms (SODA), 2020
This paper is about developing predictions for online load balancing with restricted assignments which are robust to errors. Accurate predictions yield an algorithm which goes beyond worst case bounds for this problem, but if the predictions have high error then the algorithm asymptotically matches the performance of the best algorithm in the worst case setting. To accomplish this we consider predicting a weight for each machine which then leads to a near optimal fractional assignment when the predictions are accurate. The fractional assignment is converted to an integral assignment via a novel online rounding algorithm.