Online Primal-Dual Algorithm with Predictions for Non-Linear Covering Problems
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.
Origine : Fichiers produits par l'(les) auteur(s)
Licence : CC BY NC - Paternité - Pas d'utilisation commerciale
Licence : CC BY NC - Paternité - Pas d'utilisation commerciale