@online{Antoniadis2304.01781,
TITLE = {Mixing Predictions for Online Metric Algorithms},
AUTHOR = {Antoniadis, Antonios and Coester, Christian and Eli{\'a}{\v s}, Marek and Polak, Adam and Simon, Bertrand},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2304.01781},
EPRINT = {2304.01781},
EPRINTTYPE = {arXiv},
YEAR = {2023},
MARGINALMARK = {$\bullet$},
ABSTRACT = {A major technique in learning-augmented online algorithms is combining<br>multiple algorithms or predictors. Since the performance of each predictor may<br>vary over time, it is desirable to use not the single best predictor as a<br>benchmark, but rather a dynamic combination which follows different predictors<br>at different times. We design algorithms that combine predictions and are<br>competitive against such dynamic combinations for a wide class of online<br>problems, namely, metrical task systems. Against the best (in hindsight)<br>unconstrained combination of $\ell$ predictors, we obtain a competitive ratio<br>of $O(\ell^2)$, and show that this is best possible. However, for a benchmark<br>with slightly constrained number of switches between different predictors, we<br>can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be<br>adapted to access predictors in a bandit-like fashion, querying only one<br>predictor at a time. An unexpected implication of one of our lower bounds is a<br>new structural insight about covering formulations for the $k$-server problem.<br>},
}