Improving Online Algorithms via ML Predictions
This work addresses the challenge of making online algorithms more efficient for computational tasks, though it appears incremental as it builds on classical problems with a new twist.
The paper tackled the problem of enhancing online algorithms by integrating machine-learned predictions, focusing on ski rental and non-clairvoyant job scheduling, resulting in new algorithms that improve with better predictions and maintain robustness against poor predictions.
In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.