A Learning Perspective on Random-Order Covering Problems
Anupam Gupta, Marco Molinaro, Matteo Russo · 2025
Read A Learning Perspective on Random-Order Covering Problems by Anupam Gupta, Marco Molinaro, Matteo Russo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07283.txt.
Description
Anupam Gupta, Marco Molinaro, and Matteo Russo expose a concrete bridge between online covering problems and online learning. In random-order set cover, a worst-case instance is fixed but its elements arrive in uniformly random order, and the question is how much that randomness helps against known hardness for adversarial order. A 2021 algorithm answered it with a method inspired by multiplicative weights, though its analysis argued from first principles.
The authors show the connection is exact: regret bounds for stochastic mirror descent and online convex optimization translate, by a clean recipe, into competitiveness guarantees for random-order covering. The translation extends to covering integer programs, set multicover, and non-metric facility location, matching earlier applications of the original system while giving simpler proofs. Learning theory and online algorithms emerge as two views of one mechanism.
Catalog record
| CREATOR | Anupam Gupta, Marco Molinaro, Matteo Russo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07283