Summary: 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 by R. A. Carrasco et al., Lect. Notes Comput. Sci. 10807, 245–259 (2018; Zbl 1485.68316)] 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).
For the entire collection see [Zbl 1445.68017].