A Tight $\widetilde \Omega (\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover
Online set cover is a fundamental problem in online algorithms, admitting a deterministic $O(\log m\log n)$-competitive algorithm, where $m$ is the number of sets and $n$ is the number of elements. This is essentially tight for deterministic algorithms as well as for polynomial-time randomized algorithms assuming $\mat...