2026-07-22T05:41:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12874 2024-03-06T10:50:57Z ddc:004 open_access

Set Cover with Delay - Clairvoyance Is Not Required Azar, Yossi Chiplunkar, Ashish Kutten, Shay Touitou, Noam Set Cover Delay Clairvoyant 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 Ω(√{log n}) and Ω(√{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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yossi Azar and Ashish Chiplunkar and Shay Kutten and Noam Touitou 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.8 urn:nbn:de:0030-drops-128749 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode