Learning-Augmented Online Algorithms: The Case for the Infused Advice Model and an Application to Datacenter Switch Buffer Sharing with ML Predictions
In practice, many online algorithms outperform their theoretical worst-case guarantees assured by the competitive ratio: the algorithms seem to “enjoy a good fortune”. In this talk, I will make the case for the infused advice model which allows us to shed light on the beyond worst-case performance of randomized online algorithms. The crux of the infused advice approach is that unlike existing advice/predictions models, it does not require the development of new algorithms. This also enables the empirical study of online algorithms benefitting from ML predictions. I will further discuss promising practical applications for learning-augmented online algorithms in the context of communication networks, in particular buffer sharing in datacenters.