Improving Online Algorithms via ML Predictions

By Manish Purohit, Zoya Svitkina, Ravi Kumar. Neural Information Processing Systems, 2024

410 citations recorded by the source corpus.

In this work we study the problem of using machine-learned predictions to improve 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.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/68bc259a5eba4182c98d92f0242b13457fa8d69b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Secretary and Online Matching Problems with Machine Learned Advice (2020, methodology): “ation, such as the area of prophet inequalities. Finally, we give a short overview of related problems that have been analyzed with the inclusion of machine learned advice following the frameworks in [32, 38], which we study here as well. Approximation algorithms for the matroid secretary problem. T”
Algorithms with predictions (2020, background): “Additionally Purohit et al. (2018) demonstrated explicit trade-oﬀs between these two concepts in the context of ski-rental and online scheduling.”
Secretaries with Advice (2020, background): “Examples range from building better data structures [22, 28], to improved competitive and approximation ratios for several online tasks [23, 24, 26, 29, 30, 31], to cases where advice has been used to speed-up algorithms [1, 5] or to reduce their space complexity [19].”
AdaLead: A simple and robust adaptive greedy search algorithm for sequence design (2020, methodology): “We evaluate the algorithms on a set of criteria designed to be relevant to both the biological applicability as well as the soundness of the algorithms considered (Purohit et al., 2018).”