Online Covering with Multiple Experts
This work addresses a central challenge in online algorithm research by providing a new method to combine multiple experts dynamically, which is incremental but offers a fresh perspective on integrating predictions.
The paper tackles the problem of designing online algorithms with multiple experts, moving beyond the static best expert benchmark by proposing a dynamic benchmark of linear combinations of predictions over time. It presents a competitive algorithm with a performance guarantee of O(log K) for 0-1 online optimization problems, where K is the number of experts.
Designing online algorithms with machine learning predictions is a recent technique beyond the worst-case paradigm for various practically relevant online problems (scheduling, caching, clustering, ski rental, etc.). While most previous learning-augmented algorithm approaches focus on integrating the predictions of a single oracle, we study the design of online algorithms with \emph{multiple} experts. To go beyond the popular benchmark of a static best expert in hindsight, we propose a new \emph{dynamic} benchmark (linear combinations of predictions that change over time). We present a competitive algorithm in the new dynamic benchmark with a performance guarantee of $O(\log K)$, where $K$ is the number of experts, for $0-1$ online optimization problems. Furthermore, our multiple-expert approach provides a new perspective on how to combine in an online manner several online algorithms - a long-standing central subject in the online algorithm research community.