文章基本信息
- 标题：Set Cover with Delay - Clairvoyance Is Not Required
- 本地全文：下载
- 作者：Yossi Azar ; Ashish Chiplunkar ; Shay Kutten 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：173
- 页码：8:1-8:21
- DOI：10.4230/LIPIcs.ESA.2020.8
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 Ω(â^S{log n}) and Ω(â^S{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).
- 关键词：Set Cover; Delay; Clairvoyant
