{"ID":2897084,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.06032","arxiv_id":"2507.06032","title":"Learning-Augmented Online Covering Problems","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 $ρ(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.","short_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 $ρ(k, \\cdot)$ depending on $k$, the number of arriving requests, into an algorithm with competitive ratio of...","url_abs":"https://arxiv.org/abs/2507.06032","url_pdf":"https://arxiv.org/pdf/2507.06032v1","authors":"[\"Afrouz Jabal Ameli\",\"Laura Sanita\",\"Moritz Venzin\"]","published":"2025-07-08T14:34:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}