Abstract: We give a polynomial time algorithm for Online Set Cover with a competitive ratio of $O(\log(mn))$ when the elements are revealed in random order, essentially matching the best possible offline bound of $O(\log n)$ and circumventing the $\Omega(\log(m)\log(n))$ lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order. The algorithm is a multiplicative-weights-based round-and-solve approach we call Learn-Or-Cover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for Set Cover that performs a single pass through the elements, which may be of independent interest.

This is joint work with Anupam Gupta and Gregory Kehne.