Learning-Augmented Online Covering Problems

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.

Many real-world systems must make decisions online, without knowing future requests in advance. Examples include deciding how to connect users in a communication network, which facilities to open to serve customers, or which resources to allocate as demands arrive over time. Classical online algorithms are designed to perform well even in the worst case, but this often leads to overly conservative solutions. In this work, we study how to improve online algorithms using predictions about future requests. We develop a general and mathematically rigorous framework that can incorporate such predictions in a simple black-box way. Our method automatically transforms a broad class of online covering algorithms into learning-augmented algorithms whose performance depends on the prediction error rather than on the total number of requests. As a result, when predictions are accurate, the algorithms can significantly outperform classical worst-case guarantees, while still remaining robust when predictions are inaccurate. Our framework applies to many fundamental optimization problems, including set cover, facility location, Steiner tree and forest problems, and network design problems. In several cases, this yields the first learning-augmented algorithms known for these settings. We also complement our theoretical results with experiments on online set cover instances, demonstrating substantial practical improvements even when predictions are imperfect.