Online Primal-Dual Algorithm with Predictions for Non-Linear Covering Problems - 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 Primal-Dual Algorithm with Predictions for Non-Linear Covering Problems

Enikő Kevi
Nguyễn Kim Thắng

Résumé

Designing online algorithms with predictions is a recent technique for various practically relevant online problems (scheduling, caching (paging), clustering, ski rental, etc.). [8] provided a unified approach through a primal-dual framework for linear covering problems. Their framework extends the online primal-dual method by incorporating predictions, and its performance goes beyond the worst-case analysis. Following this research line, our paper presents competitive algorithms with predictions for non-linear covering problems, generalizing the previous technique. We illustrate the applicability of our algorithms through experiments on energy minimization, congestion management, and submodular minimization problems.
Fichier principal
Vignette du fichier
main.pdf (662.45 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-04361128 , version 1 (22-12-2023)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

  • HAL Id : hal-04361128 , version 1

Citer

Enikő Kevi, Nguyễn Kim Thắng. Online Primal-Dual Algorithm with Predictions for Non-Linear Covering Problems. 2023. ⟨hal-04361128⟩
67 Consultations
36 Téléchargements

Partager

Gmail Facebook X LinkedIn More