Random Order Set Cover is as Easy as Offline

Anupam Gupta, Gregory Kehne, Roie Levin

We give a polynomial-time algorithm for OnlineSetCover with a competitive ratio of $O(\log mn)$ when the elements are revealed in random order, essentially matching the best possib…