Ravi Kumar [email protected], Manish Purohit [email protected], Zoya Svitkina (2024)
This paper investigates enhancing the performance of online algorithms through machine-learned (ML) predictions in two established problems: ski rental and non-clairvoyant job scheduling. The authors propose algorithms that are adaptive to the quality of predictions, maintaining robust performance with poor predictions while achieving optimal performance with good predictions. They introduce notions of robustness and consistency related to competitive ratios against optimal offline algorithms. The study includes a deterministic and a randomized algorithm for the ski rental problem, illustrating the use of predictions carefully to ensure robustness. For non-clairvoyant scheduling, they develop a preferential round-robin algorithm combining aspects of predicted processing times and traditional scheduling, allowing better performance than classical methods under good predictions. Experimental results indicate the algorithms significantly outperform traditional approaches with varying prediction errors.
This paper employs the following methods:
The following datasets were used in this research:
The authors identified the following limitations: