The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay
Ngoc Mai Le, Seeun William Umboh, Ningyuan Xie · Society for Industrial and Applied Mathematics eBooks · 2023
Most online problems with delay require clairvoyance, the future delay of a request is known upon its arrival, to achieve polylogarithmic competitiveness. An exception is Set Cover with Delay: Azar et al. (ESA 2020) gave a non-clairvoyant randomized algorithm with polylogarithmic competitive ratio. However, no non-trivial algorithms are known for other non-clairvoyant online problems with delay and it is also unclear if non-clairvoyance requires randomization. In this work, we make progress towards understanding the power of clairvoyance for online problems with delay by providing deterministic non-clairvoyant algorithms for Multi-Level Aggregation and Set Cover with Delay. Our main contribution is a deterministic -competitive algorithm for Multi-Level Aggregation, where D is the depth of the aggregation tree. For the special case of Joint Replenishment (D = 1), we give an lower bound against non-clairvoyant randomized algorithms. Thus, we get a tight characterization of the competitive ratio for non-clairvoyant Joint Replenishment. Finally, we show that clairvoyance is not required at all for Set Cover with Delay by derandomizing the algorithm of Azar et al. losing at most a constant factor in the competitiveness. Together with the above bounds, this also implies that randomization does not help in the non-clairvoyant setting.