  In most online problems with delay, clairvoyance (i.e. knowing the future
delay of a request upon its arrival) is required for polylogarithmic
competitiveness. In this paper, we show that this is not the case for set cover
with delay (SCD) -- specifically, we present the first non-clairvoyant
algorithm, which is $O(\log n \log m)$-competitive, where $n$ is the number of
elements and $m$ is the number of sets. This matches the best known result for
the classic online set cover (a special case of non-clairvoyant SCD). Moreover,
clairvoyance does not allow for significant improvement - we present lower
bounds of $\Omega(\sqrt{\log n})$ and $\Omega(\sqrt{\log m})$ for SCD which
apply for the clairvoyant case. In addition, the competitiveness of our
algorithm does not depend on the number of requests. Such a guarantee on the
size of the universe alone was not previously known even for the clairvoyant
case - the only previously-known algorithm (due to Carrasco et al.) is
clairvoyant, with competitiveness that grows with the number of requests. For
the special case of vertex cover with delay, we show a simpler, deterministic
algorithm which is $3$-competitive (and also non-clairvoyant).

Data Structures and Algorithms