# Learning-Augmented Online Covering Problems

arXiv: https://arxiv.org/abs/2507.06032 · HTML: https://mlsanity.com/paper/2507.06032/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)

## Abstract (arXiv)

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 ρ(k, ·) depending on k, the number of arriving requests, into an algorithm with competitive ratio of ρ(η, ·), where η 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.