Learning-Augmented Online Covering Problems

Afrouz Jabal Ameli, Laura Sanità, Moritz Venzin
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:2307-2331, 2026.

Abstract

We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online algorithm with competitive ratio $\rho(k, \cdot)$ depending on $k$, the number of arriving requests, into an algorithm with competitive ratio of $\rho(\eta, \cdot)$, where $\eta$ is the prediction error. With accurate enough prediction, the resulting competitive ratio breaks through the corresponding worst-case online lower bounds, and smoothly degrades as the prediction error grows. This framework directly applies to a wide range of well-studied online covering problems such as facility location, Steiner problems, set cover, parking permit, etc., and yields improved and novel bounds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ameli26a, title = {Learning-Augmented Online Covering Problems}, author = {Ameli, Afrouz Jabal and Sanit\`{a}, Laura and Venzin, Moritz}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {2307--2331}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ameli26a/ameli26a.pdf}, url = {https://proceedings.mlr.press/v306/ameli26a.html}, abstract = {We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online algorithm with competitive ratio $\rho(k, \cdot)$ depending on $k$, the number of arriving requests, into an algorithm with competitive ratio of $\rho(\eta, \cdot)$, where $\eta$ is the prediction error. With accurate enough prediction, the resulting competitive ratio breaks through the corresponding worst-case online lower bounds, and smoothly degrades as the prediction error grows. This framework directly applies to a wide range of well-studied online covering problems such as facility location, Steiner problems, set cover, parking permit, etc., and yields improved and novel bounds.} }
Endnote
%0 Conference Paper %T Learning-Augmented Online Covering Problems %A Afrouz Jabal Ameli %A Laura Sanità %A Moritz Venzin %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ameli26a %I PMLR %P 2307--2331 %U https://proceedings.mlr.press/v306/ameli26a.html %V 306 %X We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online algorithm with competitive ratio $\rho(k, \cdot)$ depending on $k$, the number of arriving requests, into an algorithm with competitive ratio of $\rho(\eta, \cdot)$, where $\eta$ is the prediction error. With accurate enough prediction, the resulting competitive ratio breaks through the corresponding worst-case online lower bounds, and smoothly degrades as the prediction error grows. This framework directly applies to a wide range of well-studied online covering problems such as facility location, Steiner problems, set cover, parking permit, etc., and yields improved and novel bounds.
APA
Ameli, A.J., Sanità, L. & Venzin, M.. (2026). Learning-Augmented Online Covering Problems. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:2307-2331 Available from https://proceedings.mlr.press/v306/ameli26a.html.

Related Material