License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.8
URN: urn:nbn:de:0030-drops-128749
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12874/
Azar, Yossi ;
Chiplunkar, Ashish ;
Kutten, Shay ;
Touitou, Noam
Set Cover with Delay - Clairvoyance Is Not Required
Abstract
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).
BibTeX - Entry
@InProceedings{azar_et_al:LIPIcs:2020:12874,
author = {Yossi Azar and Ashish Chiplunkar and Shay Kutten and Noam Touitou},
title = {{Set Cover with Delay - Clairvoyance Is Not Required}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {8:1--8:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12874},
URN = {urn:nbn:de:0030-drops-128749},
doi = {10.4230/LIPIcs.ESA.2020.8},
annote = {Keywords: Set Cover, Delay, Clairvoyant}
}
Keywords: |
|
Set Cover, Delay, Clairvoyant |
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
26.08.2020 |