A Learning Perspective on Random-Order Covering Problems

In the random-order online set cover problem, the instance with \(m\) sets and \(n\) elements is chosen in a worst-case fashion, but then the elements arrive in a uniformly random order. Can this random-order model allow us to circumvent the bound of \(O(\log m \log n)\)-competitiveness for the adversarial arrival order model? This long-standing question was recently resolved by [GKL21], who gave an algorithm that achieved an \(O(\log mn)\)-competitive ratio. While their LearnOrCover was inspired by ideas in online learning (and specifically the multiplicative weights update method), the analysis proceeded by showing progress from first principles.