An $\tilde{\Omega }(\log n\log m)$ Information-Theoretic Lower Bound for Randomized Online Set Cover

Abstract

We show an information-theoretic lower bound of $\Omega \left(\frac{\log n\log m}{\log \log n+\log \log m}\right)$ for online set cover against randomized algorithms, for all sufficiently large $m$ and $n$ satisfying ${\log }^{2}n\le m\le 2^n$.