Online Covering with Multiple Experts - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Online Covering with Multiple Experts

Résumé

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 multiple experts. To go beyond the popular benchmark of a static best expert in hindsight, we propose a new 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.
Fichier principal
Vignette du fichier
main.pdf (337.04 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY NC - Paternité - Pas d'utilisation commerciale

Dates et versions

hal-04297794 , version 1 (22-11-2023)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

  • HAL Id : hal-04297794 , version 1

Citer

Enikő Kevi, Nguyễn Kim Thắng. Online Covering with Multiple Experts. 2023. ⟨hal-04297794⟩
43 Consultations
29 Téléchargements

Partager

Gmail Facebook X LinkedIn More