Algorithms for Caching and MTS with reduced number of predictions

arXiv:2404.06280v1 Announce Type: new
Abstract: ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be a costly operation -- this motivated Im et al. '22 to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. '20, focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on the prediction error). Our algorithm …

abstract algorithms arxiv beyond caching case cs.ds cs.lg design performance predictions study type