A Tight $\tilde{\Omega }(\sqrt{m})$ Information-Theoretic Lower Bound for Randomized Online Set Cover

Abstract

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 $\mathrm{NP}⊈\mathrm{BPP}$. However, the best lower bound known for information-theoretic (computationally unlimited) randomized algorithms against an oblivious adversary is only $\Omega (\log m)$, whereas the upper bound in terms of $m$ is $O(\sqrt{m}\log m)=\tilde{O}(\sqrt{m})$. We prove an $\Omega (\sqrt{m})$ lower bound for information-theoretic randomized unweighted online set cover, showing that even with unbounded computational power, randomization cannot achieve an $O(\log m)$-competitive ratio. Specifically, our lower bound rules out $O(\log m\cdot {\log }^{1/2-\epsilon }n)$-competitive algorithms for every constant $\epsilon >0$. Our techniques also prove an $\Omega (m^{1/3})$ lower bound in the random-order model, and show that every algorithm with $poly(m)$ memory has competitive ratio $\Omega (m/\log m)$, even with unlimited computation between requests.