Improving Online Algorithms via ML Predictions

Abstract

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.

Conference version appeared in Neurips 2018

Cited by in corpus (12)

• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design
• Scheduling with Predictions and the Price of Misprediction
• Customizing ML Predictions for Online Algorithms
• Learning-Assisted Competitive Algorithms for Peak-Aware Energy Scheduling
• Learning-based Support Estimation in Sublinear Time
• Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
• Faster Matchings via Learned Duals
• Online Page Migration with ML Advice
• Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
• Can Q-Learning be Improved with Advice?
• Online Primal-Dual Algorithms with Predictions for Packing Problems
• Online Virtual Machine Allocation with Predictions