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